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?
Node P is the root of T
The Post-order traversal of T is: S E Q F G R P
Node Q has only one child
The left subtree of node R contains the node G
ANSWER
Statements (A) and (B) are true; (C) and (D) are false.
Official answer: A, BSource: Official answer key, GATE 2026 DA (IIT Guwahati)
The first node in the pre-order is the root, so the root of is . Statement (A) is true.
In the in-order, the nodes to the left of are (left subtree, 3 nodes) and the nodes to the right are (right subtree, 3 nodes). So the pre-order splits as , then (left subtree), then (right subtree).
Left subtree: its pre-order is , so its root is . In its in-order , lies left of and lies right of . Hence has left child and right child . Node has two children, so (C) is false.
Right subtree: its pre-order is , so its root is . In its in-order , lies left of and lies right of . Hence has left child and right child .
The left subtree of is just . Node is in the right subtree of , so (D) is false.
Post-order is left subtree, right subtree, root. Left subtree gives . Right subtree gives . Then the root . The post-order is , which matches (B), so (B) is true.
Only (A) and (B) are true.
KEY IDEA
The first node of the pre-order is the root; its position in the in-order splits the remaining nodes into the left and right subtrees. Repeat on each part, using the subtree sizes to cut the pre-order.
WATCH OUT FOR
Splitting the pre-order at the wrong place, or treating a node as having only one child without checking both sides of it in the in-order. Here has on its left and on its right, so (C) is false. Another slip is thinking is in 's left subtree, when it appears after in the in-order.
From the GATE 2026 DA paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes
