GATE CS 1987 Q2c — Trees

The statement is FALSE (represented as 0).

To uniquely construct a binary tree, we need either:

• Pre-order and In-order traversals, or
• Post-order and In-order traversals.

Pre-order and Post-order traversals are not sufficient to uniquely reconstruct a general binary tree because we cannot unambiguously determine whether a single child of a node is a left child or a right child.

Counterexample:

Consider a binary tree with two nodes, $A$ and $B$. Let:

• $\text{Pre-order} = A, B$
• $\text{Post-order} = B, A$

There are two distinct binary trees that yield these same traversals:

1. $A$ is the root, and $B$ is its left child.
2. $A$ is the root, and $B$ is its right child.

Since we cannot uniquely distinguish between these two structures, the statement is false.