Question

The set T represents various traversals over a binary tree. The set S represents the order of visiting nodes during a traversal.

T	S
I: Inorder	L: left subtree, node, right subtree
II: Preorder	M: node, left subtree, right subtree
III: Postorder	N: left subtree, right subtree, node

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:

Inorder visits the node between its subtrees, Preorder visits the node first, and Postorder visits the node last.

Answer 1

The Correct Option is A

Step 1: Recall the definitions of the three standard tree traversals.
Inorder traversal visits nodes in the order: left subtree, then the node itself, then right subtree. Preorder traversal visits the node first, then the left subtree, then the right subtree. Postorder traversal visits the left subtree, then the right subtree, and the node last.

Step 2: Match each definition in T against the descriptions in S.
Description L says "left subtree, node, right subtree", which is exactly the Inorder pattern, so I - L. Description M says "node, left subtree, right subtree", which is exactly the Preorder pattern (node visited first), so II - M. Description N says "left subtree, right subtree, node", which is exactly the Postorder pattern (node visited last), so III - N.

Step 3: Combine the matches.
I - L, II - M, III - N is exactly option (A).

Step 4: Why the other options are wrong.
Option (B), I - M, II - L, III - N, swaps Inorder and Preorder, incorrectly claiming Inorder visits the node first, but Inorder actually visits the node in the middle, between the two subtrees. Option (C), I - N, II - M, III - L, wrongly assigns Postorder's node-last pattern to Inorder and Inorder's left-node-right pattern to Postorder, reversing their true order of node visitation. Option (D), I - L, II - N, III - M, keeps Inorder correct but swaps Preorder and Postorder, claiming Preorder visits the node last (pattern N) and Postorder visits the node first (pattern M), which is exactly backwards from their definitions.

Final Answer:
Inorder matches L, Preorder matches M, and Postorder matches N.
\[ \boxed{\text{I - L, II - M, III - N (option A)}} \]