Binary Trees — Traversals and BST Maintenance: 25-Comp-A4 Program Design and Data Structures, December 2016, Q9

Question 9: Binary Trees — Traversals and BST Maintenance (20 marks: (a) 10, (b) 10)

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.

Check: the question's own stated BST rule ("smaller than its right child... greater than its left child") describes only the immediate parent–child relationship, not the standard whole-subtree BST invariant (every node in a left subtree less than the ancestor, every node in a right subtree greater). The given example tree happens to satisfy the standard, stronger definition as well — every key in 16's subtree (16, 17, 20) is <22 and every key in 28's subtree (24, 28, 33, 36) is >22, and likewise recursively within each subtree — so the answer below uses the standard whole-subtree definition, since that is what makes binary search on the tree valid at all, and is almost certainly the intended meaning.

Given. (a) The 7-node general binary tree pictured. (b) The 8-node BST pictured (root 22).

Find. (a) Its inorder, preorder and postorder sequences. (b) The tree after insert(34), then delete(33), then insert(33), each applied by the standard BST algorithms.

Approach. (a) Apply the three standard recursive traversal orders directly to the pictured shape. (b) Insert always walks down comparing keys until an empty child pointer is found; delete on a node with one child splices that child into the deleted node's place (no successor search needed, since neither 33 nor its replacement in this problem ever has two children).

(a) Traversals of the given tree (10 marks)

Question 9(a) — the given general binary tree (root a; b has only a right child d; f has only a left child g).

Preorder (root, left, right). Starting at a: visit a, recurse into b's subtree entirely (visit b, then d's subtree: d, e, then f's subtree: f, g), then finally visit c. $$\boxed{\text{preorder} = a,b,d,e,f,g,c}$$
Inorder (left, root, right). b has no left child, so b is visited immediately, then its right subtree rooted at d is traversed inorder (e, then d, then f's subtree inorder: g, then f), and finally a and its right child c. $$\boxed{\text{inorder} = b,e,d,g,f,a,c}$$
Postorder (left, right, root). Every node's children are fully emitted before the node itself: e then g then f then d (closing d's subtree), then b (closing b's subtree), then c, then finally the root a. $$\boxed{\text{postorder} = e,g,f,d,b,c,a}$$

(b) BST insert(34), delete(33), insert(33) (10 marks)

Given BST (root 22).

Insert 34. Standard BST insert walks from the root, going right whenever the new key is larger: $34>22\Rightarrow$ right to 28; $34>28\Rightarrow$ right to 36; $34<36\Rightarrow$ left to 33; $34>33$ and 33 has no right child, so 34 becomes 33's new right child.

After insert(34): 34 becomes the right child of 33 (highlighted).

$$\boxed{\text{insert}(34) \Rightarrow 34 \text{ is the right child of } 33}$$
Delete 33. Node 33 has exactly one child (34, its right child; no left child), so the standard one-child deletion rule applies: 33 is removed and its single child, 34, is spliced directly into 33's former position — 34 becomes 36's new left child, and no successor search is needed since a one-child node's deletion never requires one.

After delete(33): 34 (highlighted) takes 33's place as 36's left child.

$$\boxed{\text{delete}(33) \Rightarrow 34 \text{ takes 33's place as the left child of } 36}$$
Insert a new node with key 33. From the root: $33>22\Rightarrow$ right to 28; $33>28\Rightarrow$ right to 36; $33<36\Rightarrow$ left to 34; $33<34$ and 34 has no left child, so the new 33 becomes 34's left child — note this new 33 lands in a different tree position than the original one deleted in the previous step (as 34's child, not 36's).

After re-inserting 33: it becomes the left child of 34 (highlighted) — a different position than before deletion.

$$\boxed{\text{insert}(33) \Rightarrow 33 \text{ is the left child of } 34}$$

Question 9 — results
Item	Result
(a) Preorder	a, b, d, e, f, g, c
(a) Inorder	b, e, d, g, f, a, c
(a) Postorder	e, g, f, d, b, c, a
(b) After insert(34)	34 is right child of 33
(b) After delete(33)	34 replaces 33 as left child of 36
(b) After insert(33)	33 is left child of 34

Concept & Theory

Topic. The three classical depth-first tree traversals, and the standard BST insert/delete algorithms.

Key relations. Preorder/inorder/postorder differ only in when the root is visited relative to its two subtrees (before both, between them, after both). BST delete of a node with $k$ children: $k=0$ removes it outright; $k=1$ splices the single child into its place; $k=2$ replaces its key with the inorder successor (or predecessor) and recursively deletes that (always a $\le1$-child case).

Why this works. Inorder traversal of a BST always yields keys in sorted order, which is precisely why BST insert/delete preserve the invariant: inserting at the unique empty position found by repeated less-than/greater-than comparisons keeps every node's subtree correctly bounded, and one-child deletion is safe because the spliced-in subtree's keys are already known to lie in the correct range relative to everything above the deleted node.

Common pitfall. For (a), swapping the order of a null child's "visit" step and its sibling's real subtree (e.g. treating b's missing left child as if it contributed an entry to the sequence); for (b), deleting a one-child node by the two-child successor procedure anyway (harmless here since the "successor" of a one-child node's single child is that child itself, but conceptually the wrong rule), and forgetting that a key deleted and later re-inserted does not necessarily return to its original tree position.

Source. Cormen et al., Introduction to Algorithms, 4th ed., ch. 12 (binary search trees, insert/delete) & §12.1 (traversals); Weiss, Data Structures and Algorithm Analysis in C, 2nd ed., ch. 4 (BSTs).

Question 9 of 9: Binary Trees — Traversals and BST Maintenance

Question 9: Binary Trees — Traversals and BST Maintenance (20 marks: (a) 10, (b) 10)

(a) Traversals of the given tree (10 marks)

(b) BST insert(34), delete(33), insert(33) (10 marks)