DSA: Advanced Trees
Master self-balancing trees, range query structures, tries, and other specialized tree data structures.
AVL Trees (Self-Balancing BST)
An AVL tree is a BST that stays balanced by maintaining a balance factor at every node. The balance factor equals the height of the left subtree minus the height of the right subtree and must always be -1, 0, or 1.
AVL Rotations
When an insertion or deletion makes a node's balance factor reach 2 or -2, one or two rotations restore balance.
- LL case: left-left imbalance, fix with a single right rotation
- RR case: right-right imbalance, fix with a single left rotation
- LR case: left-right imbalance, fix with left rotation on left child then right rotation on root
- RL case: right-left imbalance, fix with right rotation on right child then left rotation on root
AVL Tree with All Four Rotations
C++balance() handles all four cases. After inserting 10-20-30 (RR), a left rotation keeps the tree height at O(log n).
Red-Black Trees
A Red-Black tree is a self-balancing BST where every node is colored red or black. Five invariants guarantee that the longest root-to-leaf path is at most twice the shortest, keeping height at O(log n).
Red-Black Tree Invariants
The five rules together ensure the tree never becomes more than twice as tall as its minimum possible height.
- Every node is red or black
- The root is always black
- Every null leaf is considered black
- If a node is red, both its children must be black (no two consecutive red nodes)
- Every path from root to any null leaf has the same number of black nodes (black-height)
| Property | AVL Tree | Red-Black Tree |
|---|---|---|
| Balance guarantee | Stricter (bf in {-1,0,1}) | Looser (2x height bound) |
| Lookup speed | Slightly faster | Slightly slower |
| Insert / delete | More rotations | Fewer rotations amortized |
| Use case | Read-heavy workloads | Write-heavy workloads (std::map, std::set) |
Segment Tree (Range Queries)
A Segment Tree preprocesses an array in O(n) and answers range sum (or min/max) queries in O(log n), with O(log n) point updates. It stores aggregate values over sub-ranges in a complete binary tree.
Segment Tree Structure
Node at index i covers a range. Its left child covers the left half; its right child covers the right half. The root covers the entire array.
- Array of size 4n is sufficient to store all segment tree nodes
- Build: O(n), bottom-up from leaves to root
- Query: O(log n), split the query range across matching segments
- Update: O(log n), update the leaf, recompute all ancestors
Segment Tree: Range Sum Queries
C++Build once in O(n). Each query splits recursively into at most O(log n) segments that cover the requested range.
Lazy Propagation in Segment Tree
Without lazy propagation, a range update (add v to every element from l to r) takes O(n log n). Lazy propagation defers the update by storing a pending value at each node and pushing it down only when the node is actually visited.
Lazy Update Strategy
Store pending updates in a lazy array. Before accessing children, push the pending value down. This reduces range updates from O(n log n) to O(log n).
- lazy[node] holds the pending addition not yet applied to children
- On update: if the node range is fully covered, update tree[node] and set lazy[node]
- On query or partial update: push lazy[node] down to children first (propagate), then recurse
- Pushing down: add lazy[node] to both children and reset lazy[node] to 0
Lazy Propagation: Range Add, Range Sum
C++push() flushes the pending lazy value to children before any access. Range updates become O(log n) instead of O(n log n).
Fenwick Tree (Binary Indexed Tree)
A Fenwick Tree (BIT) supports prefix sum queries and point updates in O(log n) time with a simpler implementation and half the memory of a Segment Tree. It uses the lowest set bit of an index to navigate.
BIT Bit-Trick Navigation
The expression i & (-i) isolates the lowest set bit of i and controls how many elements each BIT cell is responsible for.
- update(i, v): add v to index i, then move to i + (i & -i) to update ancestors
- query(i): sum BIT[i], then move to i - (i & -i) to accumulate prefix sum
- Range sum [l, r] = query(r) - query(l-1)
- Memory: O(n), Build: O(n log n), Update: O(log n), Query: O(log n)
Fenwick Tree: Prefix Sum and Point Update
C++i & -i gives the size of the responsibility window. Adding it moves up; subtracting it moves to the parent prefix.
Trie (Prefix Tree)
A Trie stores strings by sharing common prefixes. Each node represents one character. Lookup, insert, and delete all take O(L) time where L is the length of the string, regardless of how many strings are stored.
Trie Structure
Each node has up to 26 children (one per lowercase letter) and a flag marking whether a complete word ends at that node.
- Insert: follow existing children, create new nodes where characters are missing
- Search: follow children character by character; return false if any child is missing
- Prefix check: same as search but do not require the isEnd flag at the last node
- Applications: autocomplete, spell checkers, IP routing tables, dictionary word lookup
Trie: Insert, Search, Prefix Check
C++search requires isEnd = true at the last character. startsWith only needs all characters to be present.
Autocomplete Using Trie
Autocomplete navigates to the node matching the given prefix and then performs a DFS from that node to collect all words that share that prefix.
Prefix DFS for Suggestions
Reach the prefix endpoint in O(L), then DFS to collect all complete words reachable from that node.
- Step 1: traverse the trie following each character of the prefix
- Step 2: if the prefix node exists, DFS from it collecting all words where isEnd = true
- Pass a running string into DFS; append characters as you go deeper
- Time: O(L + W) where L is prefix length and W is total characters in all matching words
Autocomplete with Trie DFS
C++Navigate to the prefix node first, then DFS collects every word reachable from that node by building the string character by character.
N-ary Tree
An N-ary tree is a rooted tree where each node can have any number of children. It generalises the binary tree and is used to model file systems, organisational hierarchies, and XML/HTML document trees.
N-ary Tree with Vector of Children
Each node stores a value and a vector of child pointers. Traversals work the same as binary trees but loop over all children instead of just two.
- children vector replaces left and right pointers
- Preorder: visit node, then recursively visit each child left to right
- Level-order: same queue-based BFS, enqueue all children instead of just two
- Height: 1 + max height across all children (O(n) recursive computation)
N-ary Tree: Preorder and Level Order
C++Looping over children replaces the fixed left/right pattern. Both traversals work exactly like their binary tree counterparts.
Threaded Binary Trees
A threaded binary tree repurposes the null right pointers of nodes that have no right child, making them point to the inorder successor instead. This enables O(1) space inorder traversal without a stack or recursion.
Threading Strategy
A right-threaded binary tree reuses every null right pointer as a forward thread to the inorder successor, turning null pointers into useful traversal links.
- A boolean flag (isThread) distinguishes a real right child from a thread pointer
- During inorder traversal: follow threads to advance without a stack
- Morris traversal achieves the same effect without permanently modifying the tree
- Used in systems where stack-based recursion is too expensive (embedded environments)
Threaded Binary Tree Inorder
C++isThread distinguishes a real right child from a successor thread. No stack needed for traversal.
Knowledge Check
1. What does the balance factor of an AVL tree node represent?
2. An AVL tree rebalances when the balance factor of a node becomes:
3. A Segment Tree built on an array of n elements has how many nodes?
4. What is the time complexity of a point update in a Fenwick Tree?
5. In a Trie, each node represents:
6. Lazy propagation in a Segment Tree is used to:
7. A Red-Black Tree guarantees that the longest path from root to a leaf is at most:
8. The Fenwick Tree prefix sum query for index i uses which bit trick to move to the parent?