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: Instead of quoting the definitions from memory, build one small binary tree and physically trace each traversal on it, then match the resulting visiting order to the patterns in S.

Step 2: Take a tree with root $r$, a left child $p$, and a right child $q$. Trace Inorder on this tree: visit the left subtree of $r$ first, which is just $p$, then visit $r$ itself, then visit the right subtree, which is just $q$. The order is $p, r, q$, that is left, node, right, which is pattern L. So I maps to L.

Step 3: Trace Preorder on the same tree: the rule visits the node before its subtrees, so $r$ is visited first, then its left subtree $p$, then its right subtree $q$. The order is $r, p, q$, that is node, left, right, which is pattern M. So II maps to M.

Step 4: Trace Postorder on the same tree: the rule visits both subtrees before the node, so $p$ (left) is visited, then $q$ (right), then $r$ last. The order is $p, q, r$, that is left, right, node, which is pattern N. So III maps to N.

Step 5: This trace directly gives I - L, II - M, III - N, matching option (A) exactly, with no assignment left ambiguous since each traversal produced a distinct, unmistakable visiting order on the same test tree.

Step 6: Any option that reassigns these, such as putting the node first for Inorder (option B) or claiming Postorder visits the node before its right child (option D), contradicts what actually happened when the traversal was run on the tree in steps 2 through 4.

\[ \boxed{\text{I - L, II - M, III - N (option A)}} \]