Trees

Question 1 (12 marks)

(a) Insertion trace (8 marks):

• Insert 30 → root 30.
• Insert 20 → left child. Balanced.
• Insert 10 → BF of 30 becomes +2 (left-left) → LL rotation at 30. Result:

      20
     /  \
    10   30
  

  (2 marks)
• Insert 25 → goes right of 20, left of 30. Balanced (heights ok). Tree:

      20
     /  \
    10   30
        /
       25
  

  (1 mark)
• Insert 40 → right of 30. Balanced. Tree:

      20
     /  \
    10   30
        /  \
       25   40
  

  (1 mark)
• Insert 35 → left of 40. Node 30 becomes unbalanced: right subtree heavier, and 35 inserted in left of right child → RL rotation at 30. Right-rotate 40 then left-rotate 30: (3 marks)

Final tree:

        20
       /  \
      10   35
          /  \
         30   40
              (25 attaches under 30 left)

Correct final structure (1 mark):

        20
       /   \
      10    35
           /  \
          30   40
         /
        25

(b) Balance factors (4 marks) (BF = height(left) − height(right)):

• 20: left height 1, right height 2 → BF = −1
• 10: 0
• 35: left subtree(30,25) height 2, right(40) height 1 → BF = +1
• 30: left(25) height 1, right 0 → BF = +1
• 25: 0
• 40: 0

(1 mark per correct pair of nodes; all correct = 4)

Question 2 (10 marks)

(a) Iterative inorder (6 marks):

def inorder(root):
    stack = []
    cur = root
    result = []
    while cur is not None or stack:
        while cur is not None:      # go as far left as possible
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()           # visit node
        result.append(cur.val)
        cur = cur.right             # move to right subtree
    return result

• Correct outer loop condition (2)
• Push-left inner loop (2)
• Pop-visit-go-right logic (2)

(b) Why sorted (4 marks): The BST property states every node's key is greater than all keys in its left subtree and less than all keys in its right subtree (2). Inorder visits left subtree → node → right subtree recursively (1). Thus for any node, all smaller keys are output before it and all larger keys after it; by induction this holds at every level, producing globally ascending order (1).

Question 3 (12 marks)

(a) Build max-heap (6 marks): $A=[4,10,3,5,1]$, indices 0..4. Last internal node = index 1 (⌊5/2⌋−1 = 1).

• Sift-down index 1 (value 10): children index 3(5), 4(1); 10 is largest → no change. [4,10,3,5,1] (1)
• Sift-down index 0 (value 4): children index 1(10), 2(3); largest child 10 > 4 → swap. [10,4,3,5,1]. Now value 4 at index 1: children 5,1; 5>4 → swap. [10,5,3,4,1]. (4)

Final max-heap: [10,5,3,4,1] (1)

(b) O(n) proof (6 marks): A node at height $h$ costs at most $O(h)$ work. Number of nodes at height $h$ is at most $\lceil n/2^{h+1}\rceil$. Total: $T(n) = \sum_{h=0}^{\lfloor \log n\rfloor} \frac{n}{2^{h+1}} \cdot O(h) = O\!\left(n \sum_{h=0}^{\infty} \frac{h}{2^{h}}\right).$ (3 marks for summation)

Using $\sum_{h=0}^{\infty} h/2^h = 2$ (converges): $T(n) = O(2n) = O(n).$ (3 marks for closed form + conclusion)

Question 4 (10 marks)

(a) Delete 50 (5 marks): 50 has two children → Case 3 (two children). Inorder successor = smallest in right subtree = 60. Replace 50 with 60; delete original 60 (a leaf).

        60
       /  \
     30    70
    /  \     \
   20  40    80

(5 marks: correct successor + correct restructure)

(b) Delete 30 (5 marks): 30 has two children (20, 40) → Case 3 (two children). Inorder successor = 40 (leaf). Replace 30 with 40, delete 40.

        60
       /  \
     40    70
    /        \
   20        80

Deletion of the successor 40 itself is Case 1 (leaf/no child). (5 marks)

Question 5 (10 marks)

(a) Query prefix sum i=7 (3 marks): $7 = 0111$. Steps: 7 → 7−1=6 → 6−2=4 → 4−4=0 (stop). Indices visited: 7, 6, 4. (3 marks)

(b) Update i=3 (3 marks): $3 = 0011$. 3 → 3+1=4 → 4+4=8 → 8+8=16 > 8 (stop). Indices updated: 3, 4, 8. (3 marks)

(c) O(log n) (4 marks): Each low-bit operation $i\&(-i)$ isolates the lowest set bit; each jump either clears (query) or advances by that bit, changing the number of set/position by removing one bit level each step. There are at most $\lfloor\log_2 n\rfloor + 1$ bit positions, so at most $O(\log n)$ iterations per operation. (2 for mechanism, 2 for bound reasoning)

Question 6 (6 marks)

(a) (3 marks): search(word) walks the trie character by character and returns true only if the path exists and the final node is flagged as end-of-word. startsWith(prefix) walks the path and returns true if the path merely exists, ignoring the end-of-word flag.

(b) (3 marks): Insertion is $O(L)$ — one node traversal/creation per character. It is independent of $n$ because navigation is by character index within a fixed alphabet, not by comparing against stored words; each step is a direct child lookup, unaffected by how many other words share nodes.

[
  {"claim":"Bottom-up heapify of [4,10,3,5,1] yields max-heap [10,5,3,4,1]","code":"a=[4,10,3,5,1]\nn=len(a)\ndef sift(a,i,n):\n    while True:\n        l=2*i+1; r=2*i+2; big=i\n        if l<n and a[l]>a[big]: big=l\n        if r<n and a[r]>a[big]: big=r\n        if big==i: break\n        a[i],a[big]=a[big],a[i]; i=big\nfor i in range(n//2-1,-1,-1): sift(a,i,n)\nresult = a==[10,5,3,4,1]"},
  {"claim":"Fenwick prefix-query at i=7 visits indices [7,6,4]","code":"i=7; seq=[]\nwhile i>0:\n    seq.append(i); i-= i&(-i)\nresult = seq==[7,6,4]"},
  {"claim":"Fenwick point-update at i=3 size 8 visits indices [3,4,8]","code":"i=3; n=8; seq=[]\nwhile i<=n:\n    seq.append(i); i+= i&(-i)\nresult = seq==[3,4,8]"},
  {"claim":"Sum h/2^h from h=0 to infinity equals 2","code":"h=symbols('h')\nresult = summation(h/2**h,(h,0,oo))==2"}
]