Question

The set T represents various traversals over a binary tree. The set S represents the order of visiting nodes during a traversal. Which one of the following is the correct match from T to S?

• A. I - L, II - M, III - N
• B. I - M, II - L, III - N
• C. I - N, II - M, III - L
• D. I - L, II - N, III - M

Hint:

To remember easily: "Pre", "In", and "Post" refer to the position of the root node. In all three, the Left subtree is always visited before the Right subtree.

Answer 1

The Correct Option is A

Step 1: Understanding the Concept:
Binary tree traversal involves visiting all nodes of a tree in a specific hierarchical order. Depth-first traversals are categorized based on when the root node is visited relative to its subtrees.
Step 2: Key Formula or Approach:
The standard traversal rules are:
- Inorder: Left Subtree $\rightarrow$ Node $\rightarrow$ Right Subtree.
- Preorder: Node $\rightarrow$ Left Subtree $\rightarrow$ Right Subtree.
- Postorder: Left Subtree $\rightarrow$ Right Subtree $\rightarrow$ Node.
Step 3: Detailed Explanation:
Let's match the sets T and S based on the table provided in the image:
1. I (Inorder): The sequence is left subtree, node, then right subtree. This matches with L.
2. II (Preorder): The sequence starts with the node, followed by the left and right subtrees. This matches with M.
3. III (Postorder): The sequence visits the subtrees first and the node last. This matches with N.
Thus, the correct mapping is I-L, II-M, III-N.
Step 4: Final Answer:
The correct option is (A).