Binary Trees — Traversals and Reconstruction: 25-Comp-A4 Program Design and Data Structures, December 2017, Q8

Question 8: Binary Trees — Traversals and Reconstruction (20 marks: (a) 15, (b) 5)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) The pictured 9-node binary tree (root F; F→D,A; D→C,Q; C→(E,—); Q→(S,—); A→(—,V); V→(X,—)). (b) Preorder $1,8,12,25,13,7,9$ and inorder $8,1,25,12,7,13,9$ of a 7-node tree with all-distinct values.

Find. (a) The preorder, inorder and postorder sequences of the pictured tree. (b) The unique tree consistent with both given traversals.

Approach. (a) Apply the three standard recursive definitions (root position relative to the two subtree traversals) directly to the pictured structure. (b) Use the standard preorder+inorder reconstruction algorithm: the first preorder value is always the (sub)tree's root; its position in the corresponding inorder slice splits that slice into the left- and right-subtree inorder sequences, whose sizes then split the remaining preorder values the same way, recursively.

(a) Traversals of the pictured tree (15 marks)

The pictured tree: root F; left subtree rooted at D (children C, Q; C has left-only child E; Q has left-only child S); right subtree rooted at A (right-only child V, which itself has left-only child X).

Preorder (root, left, right). Starting at F: visit F, then the whole left subtree (D first, then C's subtree C,E, then Q's subtree Q,S), then the whole right subtree (A, then V, then X). $$\boxed{\text{preorder}=F,D,C,E,Q,S,A,V,X}$$
Inorder (left, root, right). C's subtree contributes $E,C$ (E is C's only, left, child); Q's subtree contributes $S,Q$ (S is Q's only, left, child); D's subtree is therefore $E,C,D,S,Q$; V's subtree is $X,V$ (X is V's only, left, child) and A has no left child, so A's subtree is $A,X,V$; the whole tree is D's inorder, then F, then A's inorder. $$\boxed{\text{inorder}=E,C,D,S,Q,F,A,X,V}$$
Postorder (left, right, root). C's subtree: $E,C$; Q's subtree: $S,Q$; D's subtree: $E,C,S,Q,D$; V's subtree: $X,V$; A's subtree: $X,V,A$; whole tree: D's subtree, then A's subtree, then F. $$\boxed{\text{postorder}=E,C,S,Q,D,X,V,A,F}$$

(b) Reconstructing the tree (5 marks)

Split on the root at each level. Preorder's first value, 1, is the root; in the inorder list $8,1,25,12,7,13,9$, value 1 sits after just $\{8\}$, so the left subtree is the single node 8 and the right subtree's inorder is $25,12,7,13,9$ (5 nodes). The next preorder value after the 1 left-subtree node, 12, is therefore the right subtree's root; in $25,12,7,13,9$ it splits into left $\{25\}$ and right $\{7,13,9\}$. The next preorder value, 13, is that right-right subtree's root, splitting $7,13,9$ into left $\{7\}$ and right $\{9\}$.
Draw the resulting tree.

The reconstructed tree T: root 1 (left child 8, a leaf; right child 12); 12's left child is 25 (a leaf) and right child is 13; 13's left child is 7 and right child is 9 (both leaves).

Re-deriving preorder and inorder from this tree reproduces exactly the two sequences given in the question ($1,8,12,25,13,7,9$ and $8,1,25,12,7,13,9$), confirming the reconstruction. $$\boxed{T:\ 1(8,\ 12(25,\ 13(7,9)))}$$

Question 8 — results
Item	Result
(a) Preorder	F, D, C, E, Q, S, A, V, X
(a) Inorder	E, C, D, S, Q, F, A, X, V
(a) Postorder	E, C, S, Q, D, X, V, A, F
(b) Reconstructed tree	root 1; left leaf 8; right subtree 12(25, 13(7,9))

Concept & Theory

Topic. The three depth-first binary-tree traversal orders, and unique tree reconstruction from preorder+inorder.

Key relations. Preorder = root, T(left), T(right); Inorder = T(left), root, T(right); Postorder = T(left), T(right), root. Reconstruction: preorder[0] is always the current subtree's root; its index in the current inorder slice gives the left-subtree size, which slices both the preorder and inorder arrays for the recursive calls.

Why this works. Preorder alone or inorder alone cannot determine a tree's shape (many trees share one traversal), but preorder fixes each subtree's root while inorder fixes the left/right split at every level, and together the recursion is uniquely determined at each step, which is exactly why the question states "there is only one tree $T$."

Common pitfall. In (a), reading a single-child edge off the picture as the wrong child — Q's one child S hangs to the LEFT (so Q contributes $S,Q$, not $Q,S$) and X hangs to the LEFT of V, while V itself hangs to the RIGHT of A, so A's inorder contribution is $A,X,V$, not $X,V,A$; in (b), re-using the WHOLE remaining inorder slice for both children instead of the size-matched split (must use exactly as many preorder values as the left inorder slice's length).

Source. Cormen et al., Introduction to Algorithms, 4th ed., §12.1 (binary tree traversals); Weiss, Data Structures and Algorithm Analysis in C, 2nd ed., §4.6 (tree traversal and reconstruction).

Question 8 of 9: Binary Trees — Traversals and Reconstruction

Question 8: Binary Trees — Traversals and Reconstruction (20 marks: (a) 15, (b) 5)

(a) Traversals of the pictured tree (15 marks)

(b) Reconstructing the tree (5 marks)