Question

You are given the following Pre-order and In-order traversals of a Binary Tree \(T\) with nodes E, F, G, P, Q, R, S.

Pre-order: P Q S E R F G
In-order: S Q E P F R G

Which of the following statements is/are true about the Binary Tree \(T\)?

• A. Node P is the root of T
• B. The Post-order traversal of T is: S E Q F G R P
• C. Node Q has only one child
• D. The left subtree of node R contains the node G

Hint:

Use the first element of the pre-order list as the root, then split the in-order list around it to find the left and right subtrees.

Answer 1

The Correct Option is A, B

Step 1: Find the root using the pre-order list.
In a pre-order traversal, the first node visited is always the root. The pre-order list is P Q S E R F G, so the root of the tree is P.

Step 2: Split the in-order list around the root.
In the in-order list S Q E P F R G, everything left of P belongs to the left subtree and everything right of P belongs to the right subtree. This gives left subtree in-order = S Q E and right subtree in-order = F R G.

Step 3: Split the pre-order list using the subtree sizes.
The left subtree has 3 nodes, so the next 3 entries after P in the pre-order list belong to it: Q S E. The remaining entries R F G belong to the right subtree.

Step 4: Rebuild the left subtree (nodes S, Q, E).
Left subtree pre-order = Q S E, in-order = S Q E. The first entry of this pre-order, Q, is the root of this subtree. In its in-order list S Q E, S lies to the left of Q and E lies to the right of Q. Both sides have only 1 node, so Q has a left child S and a right child E.

Step 5: Rebuild the right subtree (nodes R, F, G).
Right subtree pre-order = R F G, in-order = F R G. The first entry, R, is the root. In its in-order list F R G, F lies to the left of R and G lies to the right of R, so R has a left child F and a right child G.

Step 6: Assemble the full tree.
P is the root.
P's left child is Q, whose left child is S and right child is E.
P's right child is R, whose left child is F and right child is G.

Step 7: Check each option.
(A) Node P is the root of T: from Step 1, P is indeed the root, so this is TRUE.
(B) Post-order visits the left subtree, then the right subtree, then the root. The left subtree (rooted at Q) gives S, E, Q. The right subtree (rooted at R) gives F, G, R. Followed by the root P, the full post-order is S E Q F G R P, which matches the option exactly, so this is TRUE.
(C) Node Q has children S and E, that is two children, not one, so this statement is FALSE.
(D) The left subtree of R is just the single node F. G is R's right child, not part of R's left subtree, so this statement is FALSE.

Final Answer:
Only statements (A) and (B) are true. \[ \boxed{\text{(A) and (B)}} \]