Level 1 — RecognitionTrees

Trees

⏱ 20 minutes30 marksprintable — key stays hidden on paper

Level 1: Recognition Test

Time Limit: 20 minutes Total Marks: 30

Section A — Multiple Choice (1 mark each)

Choose the single best answer.

Q1. In a rooted tree, a node with no children is called a: (a) root (b) leaf (c) internal node (d) subtree

Q2. The number of edges on the longest path from the root to a leaf is the tree's: (a) depth of the root (b) degree (c) height (d) width

Q3. An inorder traversal of a Binary Search Tree visits keys in: (a) reverse sorted order (b) sorted (ascending) order (c) level order (d) random order

Q4. Which traversal uses a queue as its core data structure? (a) preorder (b) inorder (c) postorder (d) level-order (BFS)

Q5. In an AVL tree, the balance factor of any node must lie in the set: (a) $\{-1, 0, 1\}$ (b) $\{0, 1\}$ (c) $\{-2, -1, 0, 1, 2\}$ (d) $\{-1, 1\}$

Q6. Building a heap from an unsorted array using bottom-up heapify takes: (a) $O(n \log n)$ (b) $O(n)$ (c) $O(\log n)$ (d) $O(n^2)$

Q7. In a max-heap, the value at any node is: (a) less than both children (b) greater than or equal to its children (c) equal to its parent (d) unrelated to its children

Q8. The worst-case time to search in an unbalanced BST is: (a) $O(1)$ (b) $O(\log n)$ (c) $O(n)$ (d) $O(n \log n)$

Q9. A Trie is most naturally suited to which application? (a) shortest-path routing (b) autocomplete / prefix search (c) matrix multiplication (d) hashing integers

Q10. A Fenwick tree (BIT) supports prefix-sum query and point update each in: (a) $O(1)$ (b) $O(\log n)$ (c) $O(n)$ (d) $O(\sqrt{n})$

Q11. B-trees and B+ trees are primarily motivated by: (a) minimizing recursion depth (b) reducing disk/block accesses (c) supporting negative keys (d) avoiding pointers

Section B — Matching (5 marks)

Q12. Match each traversal/structure (left) to its defining feature (right). Write pairs like 1-a.

#	Term
1	Preorder
2	Postorder
3	Heap sort
4	Segment tree
5	Red-Black tree

Letter	Feature
a	Visits root last (Left, Right, Root)
b	Range queries with point updates, $O(\log n)$
c	Visits root first (Root, Left, Right)
d	In-place comparison sort, $O(n \log n)$
e	Balanced BST using colors + recoloring

Section C — True/False WITH Justification (2 marks each: 1 mark T/F, 1 mark justification)

Q13. "An LL imbalance in an AVL tree is fixed by a single right rotation."

Q14. "Deleting a node with two children in a BST can be done by replacing it with its inorder successor (or predecessor)."

Q15. "In a min-heap, the largest element is always at the root."

Q16. "startsWith(prefix) in a Trie can succeed even if no complete word equal to prefix was ever inserted."

Q17. "A complete binary tree with $n$ nodes has height $\Theta(n)$ ."

Q18. "Extract-max from a binary heap of $n$ elements runs in $O(\log n)$ time."

End of paper.

Answer keyMark scheme & solutions

Section A (1 mark each)

Q1 — (b) leaf. A leaf has no children by definition.

Q2 — (c) height. Height = length (edges) of longest root-to-leaf path.

Q3 — (b) sorted (ascending) order. BST property (left < node < right) makes inorder emit keys ascending.

Q4 — (d) level-order (BFS). BFS processes nodes level by level using a FIFO queue.

Q5 — (a) $\{-1,0,1\}$ . AVL keeps balance factor (height_left − height_right) within ±1; a value of ±2 triggers rotation.

Q6 — (b) $O(n)$ . Bottom-up heapify sums to $O(n)$ (tight bound $\sum h \cdot n/2^{h+1} = O(n)$ ).

Q7 — (b) greater than or equal to its children. Max-heap ordering property.

Q8 — (c) $O(n)$ . A degenerate (linked-list-shaped) BST forces linear search — motivation for balancing.

Q9 — (b) autocomplete / prefix search. Tries share prefixes along paths.

Q10 — (b) $O(\log n)$ . BIT updates/queries touch $O(\log n)$ indices via low-bit stepping.

Q11 — (b) reducing disk/block accesses. High fan-out → shallow tree → fewer block reads.

Section B (5 marks, 1 per correct pair)

Q12.

1-c (Preorder = Root, Left, Right)
2-a (Postorder = Left, Right, Root)
3-d (Heap sort = in-place, $O(n\log n)$ )
4-b (Segment tree = range query + point update, $O(\log n)$ )
5-e (Red-Black = balanced BST via coloring)

Award 1 mark per correct match.

Section C (2 marks each: 1 verdict + 1 justification)

Q13 — TRUE. LL case = insertion into left subtree of left child; a single right rotation about the unbalanced node restores balance. (1 T/F + 1 reason.)

Q14 — TRUE. The inorder successor (smallest in right subtree) preserves BST ordering when it replaces the deleted key; the successor has at most one child, reducing to an easier case. (Predecessor symmetric.)

Q15 — FALSE. A min-heap keeps the smallest element at the root; the largest sits somewhere among the leaves. (1 for FALSE, 1 for correct reason.)

Q16 — TRUE. startsWith only checks that the path spelling the prefix exists; the end node need not be flagged as a word terminator. E.g. inserting "apple" makes startsWith("app") true though "app" was never inserted. (1 + 1.)

Q17 — FALSE. A complete binary tree with $n$ nodes has height $\Theta(\log n)$ , not $\Theta(n)$ . (1 + 1.)

Q18 — TRUE. Extract-max swaps root with last leaf, removes it, then sifts down $O(\log n)$ levels. (1 + 1.)

[
  {"claim":"Complete binary tree with n=1023 nodes has height 9 (floor(log2 n))", "code":"import sympy; n=1023; result=(sympy.floor(sympy.log(n,2))==9)"},
  {"claim":"AVL balance factor set has size 3", "code":"bf={-1,0,1}; result=(len(bf)==3)"},
  {"claim":"Bottom-up heapify cost sum h*n/2^(h+1) is O(n): for n=power of 2 the finite sum stays < 2n", "code":"n=1024; import math; H=int(math.log2(n)); s=sum(h*(n//(2**(h+1))) for h in range(1,H+1)); result=(s < 2*n)"},
  {"claim":"BIT update on index touches log2(n) rounded steps <= ceil(log2 n)+1 for n=16 index=6", "code":"import math; n=16; i=6; steps=0\nwhile i<=n:\n    steps+=1; i+= i & (-i)\nresult=(steps <= math.ceil(math.log2(n))+1)"}
]