Question 6 of 9: Binary Trees — Traversals and Search-Tree Updates

Question 6: Binary Trees — Traversals and Search-Tree Updates (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.

Given. A seven-node binary tree of letters for part (a), and an eight-node binary search tree of integers for part (b), together with a three-step update sequence: insert 34, delete 33, insert 33.

Find. The three traversal orders for part (a), and the tree after each of the three updates in part (b).

Approach. Apply the three visit orders recursively to the given tree; for the search tree, follow the ordinary search path to place each insertion, and splice out the deleted node using the one-child case.

(a) The three traversals (10 marks)

[Figure not reproduced: The tree of part (a), redrawn from the paper. Note that b has no left child and f has no right child — both are the sole child on their side, which is what makes the three traversals differ so sharply. See the official exam paper.]

1. State the three visit orders. All three traversals visit every node exactly once and differ only in when the node itself is emitted relative to its subtrees: inorder is left–node–right, preorder is node–left–right, postorder is left–right–node.

   typedef struct tnode {
       char key;
       struct tnode *left, *right;
   } tnode;
   
   void inorder(const tnode *t)    /* left, node, right */
   {
       if (t == NULL) return;
       inorder(t->left);
       putchar(t->key);
       inorder(t->right);
   }
   
   void preorder(const tnode *t)   /* node, left, right */
   {
       if (t == NULL) return;
       putchar(t->key);
       preorder(t->left);
       preorder(t->right);
   }
   
   void postorder(const tnode *t)  /* left, right, node */
   {
       if (t == NULL) return;
       postorder(t->left);
       postorder(t->right);
       putchar(t->key);
   }

2. Take the inorder traversal. Descending from a, the left subtree rooted at b must be emitted first. Node b has no left child, so b comes out immediately, then its right subtree at d: within that, e (a leaf) precedes d, and d precedes its right subtree at f, in which g precedes f. That gives b, e, d, g, f for the whole left side, then the root a, then c. $$\boxed{\text{inorder: } b\;e\;d\;g\;f\;a\;c}$$
3. Take the preorder traversal. Each node is emitted on arrival, before either subtree: a, then down the left side b, d, e, then f and its only child g, and finally the root's right child c. $$\boxed{\text{preorder: } a\;b\;d\;e\;f\;g\;c}$$
4. Take the postorder traversal. Each node is emitted only after both of its subtrees are complete, so the leaves surface first and the root is last: e and then g, f complete d's subtrees so d follows, then b, then c, and a last of all. $$\boxed{\text{postorder: } e\;g\;f\;d\;b\;c\;a}$$
5. Check the results. Each sequence must contain all seven letters exactly once, which they do. Two further checks are worth knowing: preorder always begins at the root and postorder always ends at it, and both hold here.

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

1. Insert 34 by following the search path. An insertion goes exactly where a search for the same key would have failed. Comparing at each node: $34 > 22$ go right; $34 > 28$ go right; $34 < 36$ go left; $34 > 33$ go right — and 33's right link is empty, so 34 is attached there. $$\boxed{34 \text{ becomes the right child of } 33}$$

2. Delete 33 using the one-child case. Deletion has three cases — a leaf is simply removed; a node with one child is replaced by that child; a node with two children is overwritten by its inorder successor, which is then deleted from the right subtree. After step 1, node 33 has no left child and a single right child 34, so it is the one-child case: 33 is spliced out and 34 is promoted into its position. $$\boxed{36\text{'s left child becomes } 34}$$ Splicing is valid precisely because every key in 34's subtree already lies on the same side of 36 as 33 did.

3. Insert 33 again and observe that the tree has changed. Repeating the search: $33 > 22$ right; $33 > 28$ right; $33 < 36$ left; $33 < 34$ left — and 34's left link is empty. $$\boxed{33 \text{ becomes the LEFT child of } 34}$$ The key set is identical to the tree at the end of step 1, but the shape is not: 33 now sits one level deeper, as a child of the node that was once its own child. This asymmetry — delete-then-reinsert is not the identity — is why repeated update cycles gradually unbalance an unmanaged BST, and why self-balancing variants such as AVL or red–black trees exist.
4. Verify each state. The inorder traversal of a valid BST is always the sorted key sequence. After step 1 it reads 16, 17, 20, 22, 24, 28, 33, 34, 36; after step 2, 16, 17, 20, 22, 24, 28, 34, 36; after step 3, 16, 17, 20, 22, 24, 28, 33, 34, 36. All three are sorted, so the search-tree property survived every update.