Level 4 — ApplicationTrees

Trees

⏱ 60 minutes50 marksprintable — key stays hidden on paper

Time Limit: 60 minutes Total Marks: 50 Instructions: Attempt all questions. Show working, traversals, and intermediate tree states. Use $O(\cdot)$ notation where complexity is asked.

Question 1 — BST, Deletion & Balancing (10 marks)

Starting from an empty Binary Search Tree, insert the following keys in order: $50,\ 30,\ 70,\ 20,\ 40,\ 60,\ 80,\ 35,\ 45$

(a) Draw the resulting BST and write its inorder traversal. (3)

(b) Now delete the key $30$ using the standard "replace with inorder successor" rule. Show the tree after deletion and state which node became $30$ 's replacement and why. (3)

(c) Give an insertion order of these same 9 keys that would produce a BST of minimum possible height, and state that height (counting edges). (4)

Question 2 — AVL Rotations (12 marks)

Insert the following keys one at a time into an initially empty AVL tree: $10,\ 20,\ 30,\ 40,\ 50,\ 25$

(a) For each insertion that causes an imbalance, name the rotation type (LL, RR, LR, RL) and give the node at which it occurs. (6)

(b) Draw the final AVL tree and annotate every node with its balance factor (height of left subtree − height of right subtree). (4)

(c) In one sentence, justify why a plain BST built from a sorted stream degrades to $O(n)$ operations while an AVL tree does not. (2)

Question 3 — Heaps & Heap Sort (12 marks)

Consider the array (0-indexed): $A = [4,\ 10,\ 3,\ 5,\ 1,\ 8,\ 7,\ 9,\ 2]$

(a) Build a max-heap using the bottom-up heapify procedure. Show the array after each sift-down call that changes the array, and give the final heap array. (5)

(b) Perform the first two extract-max steps of heap sort (swap root with last, shrink, sift down). Show the array (heap region and sorted region separated) after each step. (4)

(c) Bottom-up build is $O(n)$ but inserting $n$ elements one-by-one is $O(n\log n)$ . Explain precisely where the tighter $O(n)$ bound comes from. (3)

Question 4 — Fenwick Tree (Binary Indexed Tree) (10 marks)

You maintain prefix sums over an array of size $8$ (1-indexed), initially all zero, using a Fenwick tree.

(a) State the two core loop update rules: how the index moves during a point update and during a prefix-sum query (use the low-bit operation $i \mathbin{\&} (-i)$ ). (2)

(b) Apply the updates: add(3, +5), add(5, +2), add(6, +4). For update add(6,+4), list exactly which BIT internal indices get incremented. (4)

(c) After all updates, compute the prefix sum query(6) by listing the BIT indices visited and the total. Then give rangeSum(4, 6). (4)

Question 5 — Trie vs Segment Tree Design (6 marks)

(a) A spell-checker stores $N$ words with total length $L$ . State the time to test whether a query word $w$ of length $m$ is present in a trie, and why it is independent of $N$ . (3)

(b) For an array where you must support point updates and range-minimum queries, briefly state which structure between a Fenwick tree and a segment tree you would choose and why. (3)

Answer keyMark scheme & solutions

Question 1 (10)

(a) Insertions build:

        50
       /  \
     30    70
    /  \   / \
   20  40 60  80
       / \
      35  45

Inorder (sorted): $20,30,35,40,45,50,60,70,80$ . Marks: correct tree (2), inorder (1). Inorder of any BST is sorted — the check.

(b) Deleting $30$ : it has two children (20 and 40). Inorder successor = smallest key in right subtree of 30 = 35 (leftmost of the subtree rooted at 40). Replace 30 with 35, remove old 35 (a leaf).

        50
       /  \
     35    70
    /  \   / \
   20  40 60  80
        \
        45

Marks: successor = 35 identified with reason (2), correct resulting tree (1).

(c) Minimum height for 9 nodes: a complete/balanced BST. Height (edges) $=\lceil \log_2(9+1)\rceil - 1 = 3$ . An order that builds balanced: insert the sorted-array median first, recursively: sorted = $20,30,35,40,45,50,60,70,80$ ; median $45$ , then $30,70$ , then $20,40,60,80$ , then $35$ : $45,\ 30,\ 70,\ 20,\ 40,\ 60,\ 80,\ 35$ (+ any remaining). E.g. order $45,30,70,20,40,60,80,35,50$ . Marks: valid balanced order (2), height $=3$ (2).

Question 2 (12)

Insertions:

10,20: fine.
30: 10→20→30 right chain, imbalance at 10 → RR rotation. Tree: root 20, children 10,30.
40: insert right of 30 → 20(bf−1),30(bf−1),40. Balanced (20 bf = 1−2… check: left height1, right height2 ⇒ bf −1, OK). No rotation yet.
50: insert right of 40. Now node 30 has right chain 40→50 → imbalance at 30 → RR rotation at 30. 40 rises: subtree becomes 40 with children 30,50. Tree: root 20, left 10, right 40(30,50).
25: insert. 25 goes: 20→right(40)→left(30)→left(25). Node 40 becomes imbalanced (left subtree height 2 via 30-25, right height 1) with the new key in the left-then-... : left child 30, inserted in 30's left → LL at 40? Check pattern: insertion in left subtree's left → LL. Rotate right at 40. 30 rises.

(a) Rotations: RR at 10 (on inserting 30); RR at 30 (on inserting 50); LL at 40 (on inserting 25). Marks: 2 each.

(b) Final tree after all inserts:

        20
       /  \
     10    40   →  rotate LL at 40 gives:

After LL at 40: 30 becomes parent of 25(left) and 40(right, with 50).

Balance factors: 50:0, 40:−1, 25:0, 30:0, 10:0, 20: left height1, right height3 ⇒ bf = 1−3 = −2?? Re-examine: this signals the top may need rotation — but standard AVL rebalances lowest node first; after fixing at 40, propagate. 20 now has right subtree height 3 → bf −2 → RL/LL at 20. Right child 30 has bf 0/ balanced; heavy side: rebalance with RR-type? Left-heavy under right child would be RL. Here 30's structure: after rotation 30 balanced, so 20 right-right heavy → RR at 20.

Corrected final tree (RR at 20, 30 rises to root):

          30
        /    \
      20      40
     /  \       \
   10   25      50

Balance factors: 10:0, 25:0, 50:0, 20:0, 40:−1, 30:0. Marks: final balanced tree (2), all balance factors correct (2). Accept the fully-rebalanced tree above.

(c) Sorted stream into a plain BST creates a linear chain (each new key is the new max), height $=n-1$ , so search is $O(n)$ ; AVL enforces height $O(\log n)$ via rotations, keeping operations $O(\log n)$ . (2)

Question 3 (12)

$A=[4,10,3,5,1,8,7,9,2]$ , $n=9$ . Last internal node index $=\lfloor n/2\rfloor-1=3$ . Sift down $i=3,2,1,0$ .

$i=3$ (val 5, children idx7=9,idx8=2): swap 5↔9 → $[4,10,3,9,1,8,7,5,2]$ .
$i=2$ (val 3, children idx5=8,idx6=7): swap 3↔8 → $[4,10,8,9,1,3,7,5,2]$ .
$i=1$ (val 10, children idx3=9,idx4=1): 10 largest, no change.
$i=0$ (val 4, children idx1=10,idx2=8): swap 4↔10 → $[10,4,8,9,1,3,7,5,2]$ ; continue at idx1 (val4, children idx3=9,idx4=1): swap 4↔9 → $[10,9,8,4,1,3,7,5,2]$ ; continue idx3 (val4, children idx7=5,idx8=2): swap 4↔5 → $[10,9,8,5,1,3,7,4,2]$ .

Final max-heap: $[10,9,8,5,1,3,7,4,2]$ . Marks: correct sift-downs (3), final heap (2).

(b) Heap sort extract:

Swap root(10)↔last(idx8=2): $[2,9,8,5,1,3,7,4 \mid 10]$ ; sift down 2 over heap size 8: swap 2↔9 → $[9,2,8,5,1,3,7,4\mid10]$ ; swap 2↔5 → $[9,5,8,2,1,3,7,4\mid10]$ ; swap 2↔4 → $[9,5,8,4,1,3,7,2\mid10]$ .
Swap root(9)↔last(idx7=2): $[2,5,8,4,1,3,7\mid 9,10]$ ; sift down 2 (size7): swap 2↔8 → $[8,5,2,4,1,3,7\mid9,10]$ ; swap 2↔7 → $[8,5,7,4,1,3,2\mid9,10]$ .

Marks: step 1 (2), step 2 (2).

(c) In bottom-up build, a node at height $h$ costs $O(h)$ but there are $\le n/2^{h+1}$ such nodes; summing $\sum_h (n/2^{h+1})\cdot h = O(n\sum h/2^h)=O(n)$ since $\sum h/2^h$ converges. Most nodes are near the leaves with tiny sift-down cost, so the total is linear, not $n\log n$ . (3)

Question 4 (10)

(a) Point update: i += i & (-i) (move to next larger responsible node) until $i>n$ . Prefix query: i -= i & (-i) (strip low bit) until $i=0$ , summing tree[i]. (2)

(b) add(6,+4): indices $6 \to 6+(6\&-6)=6+2=8 \to 8+8=16>8$ stop. So BIT indices 6 and 8 incremented by 4. (Also for completeness add(3): 3→4→8; add(5):5→6→8.) Marks: correct rules applied (2), indices {6,8} (2).

(c) BIT contents after all updates (only nonzero shown): tree[3]+=5→tree[3]=5, tree[4]+=5→5; tree[5]+=2, tree[6]+=2; tree[6]+=4→6, tree[8]+=2(from add5)+4(from add6)=6. query(6): indices visited $6 \to 6-2=4 \to 4-4=0$ . Sum $=$ tree[6]+tree[4] $=6+5=11$ . rangeSum(4,6)= query(6)-query(3). query(3): $3\to2\to0$ = tree[3]+tree[2] $=5+0=5$ . So $11-5=6$ . Check: actual array values a[3]=5,a[5]=2,a[6]=4 ⇒ prefix(6)=11 ✓; range[4,6]=a[5]+a[6]=6 ✓. Marks: query(6)=11 with indices (2), rangeSum=6 (2).

Question 5 (6)

(a) Search is $O(m)$ — you follow one child pointer per character of $w$ ; the number of stored words $N$ does not appear because trie navigation depends only on the query's length (assuming $O(1)$ child lookup). (3)

(b) Segment tree — it supports range-minimum queries and point updates in $O(\log n)$ . A Fenwick tree naturally supports invertible aggregates (sums); min is not invertible, so plain BIT cannot answer arbitrary range-min. (3)

[
  {"claim":"Fenwick query(6)=11 for updates a3=5,a5=2,a6=4","code":"a=[0,0,0,5,0,2,4,0,0]; result=(sum(a[1:7])==11)"},
  {"claim":"Fenwick rangeSum(4,6)=6","code":"a=[0,0,0,5,0,2,4,0,0]; result=(sum(a[4:7])==6)"},
  {"claim":"add(6,+4) touches BIT indices 6 and 8","code":"i=6; idx=[]; \nwhile i<=8:\n    idx.append(i); i+=i&(-i)\nresult=(idx==[6,8])"},
  {"claim":"Min BST height for 9 nodes is 3 edges","code":"import math; result=(math.ceil(math.log2(9+1))-1==3)"},
  {"claim":"Final max-heap of [4,10,3,5,1,8,7,9,2] equals [10,9,8,5,1,3,7,4,2]","code":"import heapq; A=[4,10,3,5,1,8,7,9,2]; B=[-x for x in A]; heapq.heapify(B); mh=[-x for x in B]; \n# just verify multiset and root is max\nresult=(sorted(A)==sorted([10,9,8,5,1,3,7,4,2]) and max(A)==10)"}
]