GATE 2024 DA Q.28: solution and answer

Official answer: A, B, CSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. Assume, as is standard for reconstruction questions, that every node carries a distinct label. A full binary tree is one in which every node has either $0$ or $2$ children, so no node has exactly one child.

2. Preorder + inorder (i, ii): the first preorder element is the root. Its position in the inorder sequence splits the remaining nodes into the left and right subtrees, and the subtree sizes tell us which preorder elements belong to each. Recursing on both parts rebuilds the tree uniquely. This works for any binary tree, so (A) is correct.

3. Inorder + postorder (ii, iii): the last postorder element is the root. Its position in the inorder sequence splits the nodes into the left and right subtrees, and the left size tells us which postorder elements belong to each. Recursing rebuilds the tree uniquely, for any binary tree. So (B) is correct.

4. Preorder + postorder (i, iii): for a general binary tree this pair is ambiguous, because a node with exactly one child cannot be classed as a left or a right child. For example, a root $a$ with only a left child $b$ and a root $a$ with only a right child $b$ both give preorder $a,b$ and postorder $b,a$. In a full binary tree no node has exactly one child, so this ambiguity cannot arise.

5. Reconstruction from this pair: the root is the first preorder element and also the last postorder element. If the tree has more than one node, the root has two children, and the second preorder element is the root of the left subtree. In the postorder sequence, the left subtree occupies the positions up to and including that element, because a subtree's root comes last in its own postorder block. The remaining positions, apart from the final root, form the right subtree. Recurse on each part. Every step is forced, so the tree is unique. So (C) is correct.

6. Inorder only (ii): it is not sufficient. Take the $5$-node full trees. Tree 1: root $4$, left child $2$ with leaves $1$ and $3$, right child a leaf $5$. Tree 2: root $2$, left child a leaf $1$, right child $4$ with leaves $3$ and $5$. Both are full binary trees, and both have inorder sequence $1,2,3,4,5$, yet they are different trees. So the inorder sequence alone does not determine a full binary tree, and (D) is wrong.

7. Hence (A), (B) and (C) are each sufficient and (D) is not, so the answer is A, B, C.