Level 2 — RecallTrees

Trees

⏱ 30 minutes40 marksprintable — key stays hidden on paper

Level 2 — Recall & Standard Problems Time Limit: 30 minutes Total Marks: 40

Answer all questions. Show working where required. Use clear diagrams for tree-related answers.

Q1. Define the following tree terms briefly: (a) height of a node, (b) depth of a node, (c) degree of a node, (d) leaf node. (4 marks)

Q2. For the binary tree below, write the preorder, inorder, and postorder traversals.

(6 marks)

Q3. Insert the following keys, in the given order, into an initially empty Binary Search Tree: 50, 30, 70, 20, 40, 60, 80. Draw the resulting tree, and state its inorder traversal. (4 marks)

Q4. State the BST property. Explain in one line why an inorder traversal of a BST yields keys in sorted (ascending) order. (3 marks)

Q5. Explain why a BST can degrade to $O(n)$ time for search in the worst case. Give the sequence of insertions into an empty BST that produces such a worst case for keys 1, 2, 3, 4. (4 marks)

Q6. Define the balance factor of a node in an AVL tree. For an AVL insertion, name the four rotation cases (by their standard abbreviations). (4 marks)

Q7. Consider inserting 10, 20, 30 in order into an empty AVL tree. (a) Identify which rotation case occurs. (b) Draw the balanced tree after rotation. (4 marks)

Q8. State the max-heap property. Given the array [3, 9, 2, 1, 4, 5] interpreted as a nearly-complete binary tree (0-indexed), perform bottom-up heapify to build a max-heap and write the resulting array. (5 marks)

Q9. Answer briefly: (a) State the time complexity of insert and extract-max in a binary heap. (b) State the time complexity of a point update and a range query in a Fenwick (BIT) tree. (c) Name two real-world applications of a Trie. (3 marks)

Q10. Give two properties of a Red-Black tree, and state the primary motivation for using B-trees / B+ trees over balanced BSTs. (3 marks)

End of paper

Answer keyMark scheme & solutions

Q1. (4 marks) — 1 mark each.

(a) Height of a node: the number of edges on the longest downward path from that node to a leaf. (Height of a leaf = 0.)
(b) Depth of a node: the number of edges from the root to that node. (Depth of root = 0.)
(c) Degree of a node: the number of children the node has.
(d) Leaf node: a node with no children (degree 0).

Why: height measures downward reach; depth measures distance from root — they are complementary.

Q2. (6 marks) — 2 marks each traversal.

Preorder (Root, L, R): A B D E C F
Inorder (L, Root, R): D B E A C F
Postorder (L, R, Root): D E B F C A

Why: traversal order defined by when root is visited relative to subtrees. Deduct 1 mark per misplaced node.

Q3. (4 marks) — Tree 3 marks, inorder 1 mark.

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

Inorder: 20 30 40 50 60 70 80 (sorted).

Why: each key goes left if smaller than current node, right if larger, recursively.

Q4. (3 marks)

BST property (2): For every node, all keys in its left subtree are less than the node's key, and all keys in its right subtree are greater than the node's key.
Inorder sorted (1): Inorder visits left subtree (smaller keys) → node → right subtree (larger keys), so keys emerge in ascending order.

Q5. (4 marks) — 2 marks explanation, 2 marks sequence.

Explanation: If keys are inserted in sorted (or reverse-sorted) order, no branching occurs; each new node becomes the child of the previous, forming a "skewed" tree equivalent to a linked list of height $n-1$ . Search then takes $O(n)$ .
Sequence: Inserting 1, 2, 3, 4 (ascending) into an empty BST produces a right-skewed chain:

Why: balancing (AVL/RB) is motivated precisely to avoid this degeneration.

Q6. (4 marks) — 2 marks definition, 2 marks (½ each) cases.

Balance factor of a node = height(left subtree) − height(right subtree). Must be in {−1, 0, +1} for AVL.
Four cases: LL, RR, LR, RL.

Q7. (4 marks) — 2 marks case, 2 marks tree.

(a) Inserting 10, 20, 30 makes node 10 have balance factor −2 with the imbalance down the right-right path → RR case (single left rotation).
(b) After left rotation about 10:

     20
    /  \
   10   30

Why: right-heavy chain fixed by promoting the middle key.

Q8. (5 marks) — process 3 marks, final array 2 marks. Array [3, 9, 2, 1, 4, 5], indices 0–5. Last non-leaf index = $\lfloor 6/2 \rfloor - 1 = 2$ .

i=2 (value 2): children idx4=4, idx5=5. Largest = 5. Swap → [3, 9, 5, 1, 4, 2].
i=1 (value 9): children idx3=1, idx4=4. 9 is largest, no swap.
i=0 (value 3): children idx1=9, idx2=5. Largest = 9 (idx1). Swap → [9, 3, 5, 1, 4, 2]. Now sift index1 (value 3): children idx3=1, idx4=4 → swap with 4 → [9, 4, 5, 1, 3, 2].
Final max-heap array: [9, 4, 5, 1, 3, 2].

Max-heap property (stated): every parent key ≥ its children's keys.

Why: bottom-up heapify sifts down each internal node from last to first, giving $O(n)$ build.

Q9. (3 marks) — 1 mark each part.

(a) insert: $O(\log n)$ ; extract-max: $O(\log n)$ .
(b) Fenwick point update: $O(\log n)$ ; range/prefix query: $O(\log n)$ .
(c) Any two: autocomplete / auto-suggest, spell checking, prefix search, IP routing (longest prefix match).

Q10. (3 marks) — 2 marks (any two RB properties), 1 mark motivation.

RB properties (any two): every node is red or black; the root is black; red nodes have black children (no two consecutive reds); every root-to-null path has the same number of black nodes (black-height); leaves (NIL) are black.
B-tree/B+ tree motivation: high branching factor keeps the tree very shallow, minimizing the number of expensive disk block accesses (I/O) — each node maps to one disk page.

[
  {"claim":"BST inorder of {50,30,70,20,40,60,80} is sorted", "code":"keys=[50,30,70,20,40,60,80]; result = sorted(keys)==[20,30,40,50,60,70,80]"},
  {"claim":"Worst-case skewed BST height for n=4 is n-1=3", "code":"n=4; result = (n-1)==3"},
  {"claim":"Max-heap build of [3,9,2,1,4,5] gives [9,4,5,1,3,2]", "code":"import heapq\na=[3,9,2,1,4,5]\nneg=[-x for x in a]\n# emulate array-based max-heapify result verification: check heap property of proposed array\nh=[9,4,5,1,3,2]\nok=all(h[i]>=h[2*i+1] for i in range(len(h)) if 2*i+1<len(h)) and all(h[i]>=h[2*i+2] for i in range(len(h)) if 2*i+2<len(h))\nresult = ok and sorted(h)==sorted(a)"},
  {"claim":"AVL insert 10,20,30 RR rotation yields root 20 with children 10 and 30", "code":"root=20; left=10; right=30; result = left<root<right"}
]