Data Structures & Algorithms Trees & Hierarchical Structures Syllabus

Trees & Hierarchical Structures syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Trees & Hierarchical Structures in Data Structures & Algorithms, not a summary of it.

1. 1

   Tree Fundamentals

   3 topics

   • Tree Terminology
   • Tree Traversals
   • Recursive Tree Problems
2. 2

   Binary Search Trees

   3 topics

   • BST Property and Operations
   • Insertion, Deletion, Search
   • Validation and Range Queries
3. 3

   Balanced Trees

   4 topics

   • AVL Trees
   • Red-Black Trees
   • Rotations
   • B-Trees and B+ Trees
4. 4

   Heaps & Priority Queues

   3 topics

   • Binary Heaps
   • Heap Operations
   • Top-K and K-Way Merge Problems
5. 5

   Tries & Specialized Trees

   3 topics

   • Trie (Prefix Tree)
   • Segment Trees
   • Fenwick Tree (Binary Indexed Tree)

Trees & Hierarchical Structures flashcards for Data Structures & Algorithms

23 of 50 cards from the Trees & Hierarchical Structures deck — real questions with worked answers.

1. In tree terminology, what is the difference between the *depth* and the *height* of a node?

   The **depth** of a node is the number of edges on the path from the root to that node (root has depth $0$). The **height** of a node is the number of edges on the longest path from that node down to a leaf (leaves have height $0$). The height of the tree equals the height of its root.

2. Define the following tree terms: root, leaf, internal node, sibling, and ancestor.

   **Root**: the unique node with no parent. **Leaf** (external node): a node with no children. **Internal node**: a node with at least one child. **Siblings**: nodes sharing the same parent. **Ancestor** of a node $v$: any node on the path from the root to $v$ (excluding $v$ itself for proper ancestors).

3. For a binary tree of height $h$, what are the minimum and maximum possible numbers of nodes?

   Minimum: $h+1$ nodes (a degenerate/skewed tree, one node per level). Maximum: $2^{h+1}-1$ nodes (a perfect binary tree). Thus a tree with $n$ nodes has height between $\lfloor \log_2 n \rfloor$ and $n-1$.

4. What is a *complete* binary tree, and how does it differ from a *full* and a *perfect* binary tree?

   **Complete**: every level is fully filled except possibly the last, which is filled left to right. **Full** (proper/strict): every node has either $0$ or $2$ children. **Perfect**: all internal nodes have $2$ children and all leaves are at the same depth (a perfect tree of height $h$ has exactly $2^{h+1}-1$ nodes).

5. List the three depth-first binary tree traversals and the visit order of each relative to a node's subtrees.

   **Preorder**: Node, Left, Right. **Inorder**: Left, Node, Right. **Postorder**: Left, Right, Node. (The prefix names where the node itself is visited relative to recursing on its two subtrees.)

6. Which traversal of a Binary Search Tree yields the keys in sorted ascending order, and why?

   **Inorder traversal** (Left, Node, Right). Because in a BST every key in the left subtree is smaller and every key in the right subtree is larger, visiting left-node-right recursively emits keys in nondecreasing order.

7. What traversal produces a level-by-level ordering of a tree, and what data structure implements it?

   **Breadth-first / level-order traversal**, implemented with a **FIFO queue**: enqueue the root, then repeatedly dequeue a node, visit it, and enqueue its children. Time $O(n)$, space $O(w)$ where $w$ is the maximum width.

8. Given preorder and inorder traversal sequences of a binary tree with distinct keys, can the tree be uniquely reconstructed? What about preorder + postorder?

   **Preorder + inorder** (or postorder + inorder) uniquely determines the tree. **Preorder + postorder** does NOT in general — it fails to distinguish left-only from right-only children, so it uniquely determines the tree only for full binary trees.

9. Write a recursive formula for the height of a binary tree node in terms of its children's heights.

   $$\text{height}(v) = \begin{cases} -1 & v = \text{null} \\ 1 + \max\big(\text{height}(v.\text{left}),\ \text{height}(v.\text{right})\big) & \text{otherwise} \end{cases}$$ (Using the convention height of an empty subtree $= -1$ so a single leaf has height $0$.)

10. Give the recursive definition used to count the total number of nodes in a binary tree.

    $$\text{count}(v) = \begin{cases} 0 & v = \text{null} \\ 1 + \text{count}(v.\text{left}) + \text{count}(v.\text{right}) & \text{otherwise} \end{cases}$$ Runs in $O(n)$ time and $O(h)$ recursion-stack space.

11. What is the recursive strategy for finding the Lowest Common Ancestor (LCA) of two nodes in a plain binary tree?

    Recurse into both subtrees searching for the two target nodes. If the current node is one of the targets, return it. If the left and right recursive calls both return non-null, the current node is the LCA. Otherwise return whichever side is non-null. Runs in $O(n)$.

12. State the Binary Search Tree (BST) property precisely.

    For every node $x$: all keys in $x$'s left subtree are $< x.\text{key}$, and all keys in $x$'s right subtree are $> x.\text{key}$ (assuming distinct keys). This must hold recursively for every node, not just direct children.

13. What is the time complexity of search, insert, and delete in a BST, in both the balanced and worst cases?

    All three are $O(h)$ where $h$ is the tree height. Balanced: $h = O(\log n)$, giving $O(\log n)$. Worst case (degenerate/skewed tree): $h = O(n)$, giving $O(n)$.

14. Describe the BST search algorithm for a key $k$.

    Start at the root. At each node, if $k$ equals the node's key, return it. If $k <$ node's key, go left; if $k >$ node's key, go right. Stop when you find $k$ or hit null (not present). Time $O(h)$.

15. Describe how insertion works in a BST and where the new node ends up.

    Perform a search for the key; when you reach a null child pointer, that is the insertion point. Insert the new key there as a new **leaf**. BST insertion never restructures existing nodes; it only adds a leaf. Time $O(h)$.

16. Explain the three cases of BST node deletion.

    **Case 1 (leaf)**: simply remove it. **Case 2 (one child)**: replace the node with its single child. **Case 3 (two children)**: replace the node's key with its **inorder successor** (smallest key in the right subtree) or inorder predecessor, then delete that successor node (which has at most one child).

17. How do you find the inorder successor of a node in a BST?

    If the node has a right subtree, the successor is the **leftmost node of that right subtree** (repeatedly go left). If it has no right subtree, the successor is the **lowest ancestor whose left subtree contains the node** (walk up until you move up from a left child).

18. How can you validate that a binary tree is a valid BST in $O(n)$ time?

    Recurse carrying a valid $(\text{low}, \text{high})$ range for each node: check $\text{low} < \text{key} < \text{high}$, then recurse left with range $(\text{low}, \text{key})$ and right with $(\text{key}, \text{high})$. Starting range is $(-\infty, +\infty)$. Alternatively, verify an inorder traversal is strictly increasing.

19. Why is checking only that each node is greater than its left child and less than its right child insufficient to validate a BST?

    The BST property is global, not just parent-child local. A node deep in the left subtree could still exceed an ancestor. Example: root $10$, right child $15$, but $15$'s left child is $6$ — locally valid at each pair, yet $6 < 10$ violates the BST property against the ancestor $10$.

20. How do you perform a range query (return all keys in $[lo, hi]$) on a BST efficiently?

    Recurse from the root: if the current key $> lo$, recurse left; if $lo \leq \text{key} \leq hi$, output it; if the current key $< hi$, recurse right. This prunes subtrees outside the range. Cost is $O(h + k)$ where $k$ is the number of reported keys.

21. What defines an AVL tree, and what is its balance factor constraint?

    An AVL tree is a self-balancing BST where, for **every** node, the **balance factor** $= \text{height(left)} - \text{height(right)}$ is in $\{-1, 0, +1\}$. If an insertion or deletion violates this, rotations restore balance.

22. What is the maximum height of an AVL tree with $n$ nodes?

    $h \leq 1.44 \log_2(n+2) - 0.328$, i.e. $h = O(\log n)$. The worst case relates to Fibonacci: the minimum number of nodes in an AVL tree of height $h$ is $N(h) = N(h-1) + N(h-2) + 1$, which grows like $\phi^{h}$ with $\phi = \frac{1+\sqrt{5}}{2}$.

23. Name the four rotation cases used to rebalance an AVL tree after insertion.

    **Left-Left (LL)**: single right rotation. **Right-Right (RR)**: single left rotation. **Left-Right (LR)**: left rotation on child then right rotation on node. **Right-Left (RL)**: right rotation on child then left rotation on node. Named by the path from the unbalanced node to the newly inserted node.

See more Trees & Hierarchical Structures flashcards →

Planning Trees & Hierarchical Structures for Data Structures & Algorithms

Trees & Hierarchical Structures (Data Structures & Algorithms) FAQ