GATE CS 2004 Q35 — Trees

To uniquely reconstruct a binary tree, we must be able to determine the root of each subtree and partition the remaining nodes into its left and right subtrees.

• Inorder traversal is crucial because it provides the relative left-to-right order of the nodes. For any root node, all elements appearing before it in the inorder sequence belong to its left subtree, and all elements appearing after it belong to its right subtree.
• Preorder traversal gives the root of the tree first, while Postorder traversal gives the root of the tree last.

Using these properties:

1. Inorder and Postorder (II): The last element of the postorder sequence is the root. We locate this root in the inorder sequence to split the tree into left and right subtrees. This process is applied recursively, identifying the tree uniquely.
2. Preorder and Inorder (III): The first element of the preorder sequence is the root. We locate this root in the inorder sequence to split the tree into left and right subtrees. This also reconstructs the tree uniquely.

Why other pairs fail:

• Preorder and Postorder (I): If a node has only one child, we cannot determine whether it is a left child or a right child. For example, a tree with root $A$ and left child $B$ has preorder $A, B$ and postorder $B, A$. A tree with root $A$ and right child $B$ also has preorder $A, B$ and postorder $B, A$.
• Level order and Postorder (IV): Similarly, we cannot uniquely distinguish left and right subtrees. For example, a tree with root $A$ and left child $B$ has level order $A, B$ and postorder $B, A$, which is identical to a tree with root $A$ and right child $B$.

Thus, only pairs II and III can uniquely identify a binary tree.