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: Understanding the Topic
This question involves reconstructing a unique binary tree from its preorder and inorder traversal sequences. Once the tree is reconstructed, we can determine its postorder traversal and verify other properties mentioned in the options.
Step 2: Key Approach - Recursive Tree Construction
The core principles for reconstruction are:

The first element in the preorder traversal is always the root of the (sub)tree.
The elements in the inorder traversal to the left of the root form the left subtree, and elements to the right form the right subtree.
We apply this process recursively to build the entire tree.
Step 3: Detailed Explanation
A. Find the Root of the Main Tree:
The preorder traversal is `P, Q, S, E, R, F, G`. The first element is P, so P is the root of the entire tree. (Statement C is correct, but we need to check all options.)
The inorder traversal is `S, Q, E, P, F, R, G`.

Nodes to the left of P in the inorder list (`S, Q, E`) form the left subtree.
Nodes to the right of P (`F, R, G`) form the right subtree.
B. Construct the Left Subtree:


Left subtree inorder: `S, Q, E`
Left subtree preorder (the next elements in the main preorder sequence): `Q, S, E`
The root of this subtree is Q. In the inorder list `S, Q, E`, S is to the left of Q and E is to the right. So, S is the left child of Q, and E is the right child of Q. (Statement A, "Node Q has only one child," is false.)
C. Construct the Right Subtree:


Right subtree inorder: `F, R, G`
Right subtree preorder (the remaining elements): `R, F, G`
The root of this subtree is R. In the inorder list `F, R, G`, F is to the left of R and G is to the right. So, F is the left child of R, and G is the right child of R. (Statement D, "The left subtree of node R contains node G," is false; G is in the right subtree.)
D. Determine the Postorder Traversal:
Postorder traversal visits nodes in the order: Left, Right, Root.

Postorder of left subtree (Root Q, Left S, Right E): S, E, Q
Postorder of right subtree (Root R, Left F, Right G): F, G, R
Postorder of the whole tree: (Left Subtree), (Right Subtree), (Root P) \[ \underbrace{S, E, Q}_{\text{Left}}, \underbrace{F, G, R}_{\text{Right}}, \underbrace{P}_{\text{Root}} \]
The complete postorder traversal is `S, E, Q, F, G, R, P`. (Statement B is correct.)
Step 4: Final Answer
Comparing the options, statement (B) accurately describes the postorder traversal of the reconstructed tree. Although (C) is also true, (B) is a more complete description of the tree's properties derived from the traversals.