Question 30

Given traversals:

• Postorder: 8, 9, 6, 7, 4, 5, 2, 3, 1
• Inorder: 8, 6, 9, 4, 7, 2, 5, 1, 3

Reconstruct the tree recursively:

1. The root is the last element of postorder: 1.
2. In inorder, 1 splits into left subtree $\{8, 6, 9, 4, 7, 2, 5\}$ and right subtree $\{3\}$.
   • Node 3 is a single right child of 1 (depth 1).
3. Left subtree postorder is $\{8, 9, 6, 7, 4, 5, 2\}$, so root of left subtree is 2.
   • In inorder, 2 splits into left subtree $\{8, 6, 9, 4, 7\}$ and right subtree $\{5\}$. Node 5 is right child of 2 (depth 2).
4. Subtree $\{8, 6, 9, 4, 7\}$ has root 4 (last in postorder 8, 9, 6, 7, 4).
   • In inorder, 4 splits into left subtree $\{8, 6, 9\}$ and right child 7 (depth 3).
5. Subtree $\{8, 6, 9\}$ has root 6 (last in postorder 8, 9, 6).
   • In inorder, 6 splits into left child 8 and right child 9 (both at depth 4).

The path from root 1 to leaf 8 is: $1 \to 2 \to 4 \to 6 \to 8$.
The length of this path (number of edges) is 4. Hence, the height of the binary tree is 4.