Question

Consider a binary tree whose preorder traversal is \[ P, Q, S, E, R, F, G \] and inorder traversal is \[ S, Q, E, P, F, R, G. \] Which of the following statements is correct?

• A. Node \( Q \) has only one child.
• B. Postorder traversal is \( S, E, Q, F, G, R, P \).
• C. \( P \) is the root of the tree.
• D. The left subtree of node \( R \) contains node \( G \).

Hint:

Preorder gives root first. Inorder helps split left and right subtrees. Postorder is Left–Right–Root.

Answer 1

The Correct Option is B

Step 1: Identify the root from preorder.
In preorder traversal, the first element is always the root.
Thus, root \( = P \).
Step 2: Split inorder traversal around root.
In inorder: \[ S, Q, E, P, F, R, G \] Elements left of \( P \) form left subtree: \[ S, Q, E \] Elements right of \( P \) form right subtree: \[ F, R, G \] Step 3: Construct left subtree.
From preorder after removing \( P \): \[ Q, S, E, R, F, G \] Left subtree preorder: \[ Q, S, E \] Root of left subtree \( = Q \).
In inorder left part: \[ S, Q, E \] Left of \( Q \): \( S \).
Right of \( Q \): \( E \).
Thus left subtree: \[ \text{ Q} \] \[ \text{ / \textbackslash} \] \[ \text{ S E} \] Step 4: Construct right subtree.
Remaining preorder: \[ R, F, G \] Root \( = R \).
In inorder right part: \[ F, R, G \] Left of \( R \): \( F \).
Right of \( R \): \( G \).
Step 5: Write postorder traversal.
Postorder = Left subtree, Right subtree, Root.
Left subtree postorder: \[ S, E, Q \] Right subtree postorder: \[ F, G, R \] Whole tree postorder: \[ S, E, Q, F, G, R, P \] Thus option (B) is correct.