Data Structures & Algorithms Trees & Hierarchical Structures Syllabus

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.

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}$.

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.

What are the defining properties (invariants) of a Red-Black tree?

1) Every node is red or black. 2) The root is black. 3) All leaves (NIL sentinels) are black. 4) A red node's children are both black (no two consecutive reds). 5) Every root-to-leaf path passes through the same number of black nodes (**black-height** is uniform).

What height guarantee do Red-Black trees provide, and how does it follow from the invariants?

Height $h \leq 2\log_2(n+1)$, i.e. $O(\log n)$. Because no path has two consecutive red nodes, the longest root-to-leaf path is at most twice the shortest (all-black) path, and uniform black-height bounds both.

Compare AVL trees and Red-Black trees in terms of balance strictness and use cases.

**AVL** trees are more strictly balanced (height factor $\leq 1.44\log n$), giving faster lookups but more rotations on updates — better for read-heavy workloads. **Red-Black** trees are more loosely balanced ($\leq 2\log n$) with fewer rotations per update ($O(1)$ amortized), better for insert/delete-heavy workloads. Red-Black trees back many standard-library maps/sets.

Describe a left rotation on node $x$ (with right child $y$) and what it preserves.

$y$ becomes the new subtree root; $x$ becomes $y$'s left child; $y$'s original left subtree becomes $x$'s right subtree. It preserves the BST inorder ordering and runs in $O(1)$ time by relinking a constant number of pointers. A right rotation is its mirror inverse.

Do rotations change the inorder traversal of a BST? Why does this matter?

No — rotations **preserve the inorder ordering** of keys; they only change the tree's shape/height. This is precisely why balanced BSTs (AVL, Red-Black) can rebalance via rotations without violating the BST property.

What is a B-tree of minimum degree (order) $t$, and what are its key properties?

A B-tree of minimum degree $t \geq 2$ is a balanced multiway search tree where: every node has at most $2t-1$ keys and at most $2t$ children; every non-root node has at least $t-1$ keys; keys within a node are sorted; and **all leaves are at the same depth**. Height is $O(\log_t n)$.

Why are B-trees and B+ trees preferred for databases and filesystems over binary search trees?

Their high branching factor makes them **shallow**, minimizing the number of slow disk/block accesses (each node maps to a disk page). Height $O(\log_t n)$ with large $t$ means very few I/Os per operation, unlike a binary tree's $\log_2 n$ deeper structure.

What is the key structural difference between a B-tree and a B+ tree?

In a **B-tree**, keys (and their data) live in both internal and leaf nodes. In a **B+ tree**, all actual data/records reside only in the **leaves**; internal nodes hold only separator keys for routing. B+ tree leaves are also linked in a sorted linked list, enabling fast in-order range scans.

What is a binary heap and what is the heap-order property for a min-heap vs. a max-heap?

A binary heap is a **complete** binary tree stored in an array. **Min-heap**: every parent's key $\leq$ its children's keys (root is the minimum). **Max-heap**: every parent's key $\geq$ its children's keys (root is the maximum). It gives no ordering between siblings.

For a 0-indexed array representation of a binary heap, give the index formulas for a node's parent, left child, and right child.

For index $i$: parent $= \lfloor \frac{i-1}{2} \rfloor$, left child $= 2i+1$, right child $= 2i+2$. (For 1-indexed heaps: parent $= \lfloor i/2 \rfloor$, left $= 2i$, right $= 2i+1$.)

Describe the sift-up (bubble-up) operation used when inserting into a binary heap.

Append the new element at the end of the array (next leaf position). Then repeatedly compare it with its parent; if it violates the heap order, swap them. Continue until the parent satisfies the order or the root is reached. Cost $O(\log n)$.

Describe the sift-down (heapify) operation used when extracting the root of a binary heap.

Remove the root, move the last element to the root position, then repeatedly swap it with its **smaller child** (min-heap) / larger child (max-heap) until heap order is restored or a leaf is reached. Cost $O(\log n)$. This underlies extract-min/extract-max.

What is the time complexity of building a heap from an unsorted array of $n$ elements, and why is it $O(n)$ rather than $O(n\log n)$?

**Build-heap runs in $O(n)$**. Applying sift-down from the last internal node up to the root, the work is $\sum_{h} \frac{n}{2^{h+1}} \cdot O(h) = O\!\left(n \sum_{h=0}^{\infty} \frac{h}{2^{h}}\right) = O(n)$, because most nodes are near the bottom with small sift-down cost.

Give the time complexities for the core binary heap operations: peek, insert, extract-min/max, and decrease-key.

**Peek** (find-min/max): $O(1)$. **Insert**: $O(\log n)$. **Extract-min/max**: $O(\log n)$. **Decrease-key / increase-key**: $O(\log n)$. **Build-heap**: $O(n)$. **Delete arbitrary** (given index): $O(\log n)$.

How do you find the $k$-th largest element in an array using a heap, and what is the complexity?

Maintain a **min-heap of size $k$**: iterate through elements, push each; if the heap exceeds size $k$, pop the smallest. After processing, the heap's root is the $k$-th largest. Time $O(n \log k)$, space $O(k)$. (Quickselect gives $O(n)$ average as an alternative.)

Describe the K-way merge problem and how a heap solves it efficiently.

Merge $k$ sorted lists (total $n$ elements) into one sorted output. Use a **min-heap of size $k$** holding the current front element of each list. Repeatedly pop the smallest, output it, and push the next element from that element's list. Time $O(n \log k)$, space $O(k)$.

For the Top-K frequent elements problem, describe an efficient heap-based approach and its complexity.

Count frequencies with a hash map ($O(n)$), then maintain a **min-heap of size $k$** keyed by frequency, popping the least frequent when size exceeds $k$. The heap ends holding the $k$ most frequent. Time $O(n \log k)$. (Bucket sort by frequency gives $O(n)$.)

What is a Trie (prefix tree), and what does each node/edge represent?

A Trie is a tree for storing strings where each **edge represents a character** and each path from the root spells a prefix. Nodes typically hold a map/array of child pointers and a boolean flag marking the end of a valid word. Common prefixes share the same path, saving space.

What are the time complexities of insert, search, and prefix-search (startsWith) in a Trie?

All are $O(L)$ where $L$ is the length of the query string — **independent of the number of stored words $n$**. This is the Trie's key advantage over hashing for prefix queries. Space can be large: up to $O(n \cdot L \cdot \sigma)$ with alphabet size $\sigma$ using array-based children.

Give one advantage of a Trie over a hash table for string storage.

Tries support efficient **prefix queries** (autocomplete, startsWith, longest-prefix matching) and return keys in sorted order, none of which hash tables do naturally. Lookups are $O(L)$ with no hashing collisions, and common prefixes are stored once.

What is a Segment Tree and what class of problems does it solve?

A Segment Tree is a binary tree over an array where each node stores an aggregate (sum, min, max, gcd, …) of a contiguous range. It answers **range queries and point/range updates** on a static-size array, both in $O(\log n)$, using $O(n)$ space (typically a $2n$ to $4n$ array).

State the time and space complexities for building, querying, and updating a Segment Tree.

**Build**: $O(n)$ time. **Range query**: $O(\log n)$. **Point update**: $O(\log n)$. **Range update with lazy propagation**: $O(\log n)$. **Space**: $O(n)$ (allocate about $4n$ or $2n$ for iterative).

What is *lazy propagation* in a Segment Tree and why is it needed?

Lazy propagation defers **range updates** by storing a pending update value at internal nodes and only pushing it down to children when those children are actually visited. Without it, a range update would touch $O(n)$ leaves; with it, both range update and range query stay $O(\log n)$.

What is a Fenwick Tree (Binary Indexed Tree, BIT) and what operations does it support?

A Fenwick Tree is an array-based structure supporting **prefix-sum queries** and **point updates**, each in $O(\log n)$, using only $O(n)$ space. It exploits the binary representation of indices: index $i$ is responsible for a range of length equal to its lowest set bit.

In a 1-indexed Fenwick Tree, how do you move to the next index during an update versus during a prefix-sum query?

Let $\text{lsb}(i) = i \,\&\, (-i)$ (lowest set bit). **Update** (add): move to $i \mathrel{+}= \text{lsb}(i)$, going upward covering ranges. **Prefix-sum query**: move to $i \mathrel{-}= \text{lsb}(i)$, accumulating until $i = 0$. Both take $O(\log n)$ steps.

Compare a Fenwick Tree and a Segment Tree for range-sum problems.

**Fenwick**: simpler, ~$O(n)$ space (single array), lower constant factors, but limited mostly to invertible aggregates (sums) and prefix-based queries. **Segment Tree**: more general (min/max/gcd/assignments, range updates via lazy propagation, arbitrary associative merges) at the cost of more memory (~$4n$) and code complexity. Both query/update in $O(\log n)$.

How is a range-sum $\text{sum}(l, r)$ over indices $l..r$ computed from a Fenwick Tree that supports prefix sums?

Using prefix sums $P(i) = \text{sum}(1..i)$: $$\text{sum}(l, r) = P(r) - P(l-1).$$ Each prefix sum is $O(\log n)$, so a range-sum query is $O(\log n)$. This subtraction trick requires an invertible operation (why Fenwick suits sums but not min/max directly).