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

The trick with pre-order and in-order pairs is that the root always sits at the front of the pre-order list, and it splits the in-order list into a left part and a right part. Apply that rule repeatedly to draw the tree, then check each statement against the drawing.

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

The root is $P$, the first pre-order entry. In the in-order list, $P$ sits between "S Q E" (left side) and "F R G" (right side), so the left subtree holds nodes {S, Q, E} and the right subtree holds {F, R, G}.

Matching the pre-order list to these two groups, the left group takes the next 3 letters after P, which is "Q S E", and the right group takes what remains, "R F G".

For the left piece (pre-order Q S E, in-order S Q E): the root is $Q$, with S to its left and E to its right in the in-order list, so $Q$ has two children, left = S and right = E.

For the right piece (pre-order R F G, in-order F R G): the root is $R$, with F to its left and G to its right, so $R$ has two children, left = F and right = G.

So the tree looks like this: P is the root; the left child of P is Q, with left child S and right child E; the right child of P is R, with left child F and right child G.

Now check each statement:

1. (A) P is the root: confirmed directly above, so this is correct.
2. (B) Post-order is S E Q F G R P: post-order visits left child, right child, then the node itself. For the Q-subtree that gives S, E, Q. For the R-subtree that gives F, G, R. Putting the root P last gives S E Q F G R P, which matches, so this is correct.
3. (C) Q has only one child: Q has both S and E as children, so this is wrong.
4. (D) G lies in the left subtree of R: R's left subtree is just F; G is R's right child, so this is wrong.

The correct statements are (A) and (B).

\[ \boxed{\text{(A) and (B)}} \]