TAOCP 2.3.1 Exercise 7

Section 2.3.1: Traversing Binary Trees

Exercise 7. [22] Show that if we are given the preorder and the inorder of the nodes of a binary tree, the binary tree structure may be constructed. (Assume that the nodes are distinct.) Does the same result hold true if we are given the preorder and postorder, instead of preorder and inorder? Or if we are given the inorder and postorder?

Verified: no
Solve time: 27s

Solution

Let the preorder of the binary tree be $u_1 u_2 \dots u_n$ and the inorder be $v_1 v_2 \dots v_n$. Assume all nodes are distinct. We show that these two sequences determine the binary tree uniquely, and then discuss the analogous questions for other pairs of traversal orders.

We proceed by induction on $n$. If $n = 0$, the tree is empty and the statement holds trivially. Assume $n > 0$.

Let $r = u_1$ be the first node in the preorder sequence; by definition of preorder, $r$ is the root of the tree. Locate $r$ in the inorder sequence at position $k$, so $v_k = r$. Then the nodes $v_1 \dots v_{k-1}$ form the inorder sequence of the left subtree, and the nodes $v_{k+1} \dots v_n$ form the inorder sequence of the right subtree. Let the left subtree contain $k-1$ nodes and the right subtree $n-k$ nodes.

The preorder sequence of the left subtree is $u_2 \dots u_k$, since these are the first $k-1$ nodes following the root in preorder, and the preorder sequence of the right subtree is $u_{k+1} \dots u_n$. By the induction hypothesis, the left and right subtrees are uniquely determined from their respective preorder and inorder sequences. Finally, attaching these two subtrees to the root $r$ reconstructs the entire tree uniquely.

Hence the binary tree is uniquely determined by its preorder and inorder sequences.

We now consider the pair preorder and postorder. Let $u_1 \dots u_n$ be the preorder and $w_1 \dots w_n$ the postorder. The root is $u_1 = w_n$. The next node in preorder, $u_2$, is the root of the left subtree. However, the postorder sequence only informs us that the left subtree's nodes occur before the right subtree's nodes in postorder, without indicating the boundary between left and right subtrees unless the left subtree contains exactly one node. Therefore, multiple different binary trees may have the same preorder and postorder sequences. A simple counterexample is:

Preorder:  A B C
Postorder: B C A

Here two distinct trees realize these sequences: either $A$ with left child $B$ and right child $C$, or $A$ with left child $B$ and $B$ having right child $C$. Thus preorder and postorder do not determine the tree uniquely.

Finally, consider inorder and postorder. Let $v_1 \dots v_n$ be inorder and $w_1 \dots w_n$ be postorder. The last node of postorder, $w_n$, is the root $r$. Locate $r$ in the inorder sequence at position $k$, so $v_k = r$. Then $v_1 \dots v_{k-1}$ are the nodes of the left subtree, and $v_{k+1} \dots v_n$ are the nodes of the right subtree. The postorder sequence of the left subtree is $w_1 \dots w_{k-1}$, and the right subtree is $w_k \dots w_{n-1}$. By induction on the size of the subtrees, both subtrees are uniquely determined. Attaching them to the root reconstructs the tree uniquely. Therefore inorder and postorder together also determine the binary tree uniquely.

This completes the proof.

∎

$$ \boxed{ \text{Preorder + Inorder: uniquely determines the tree; Preorder + Postorder: does not; Inorder + Postorder: uniquely determines the tree.} } $$