Segment Tree
A segment tree answers range queries (range sum, range minimum) in O(log n) and supports point or range updates in O(log n). Build: recursively split the array in half. Each node stores the aggregate (sum, min, max) for its range. Leaf nodes store individual elements. Build time: O(n). Space: O(4n) for the array-based representation.
Range sum query: if the query range covers the node’s range entirely — return the node’s value. If no overlap — return 0 (identity). Otherwise recurse on both children and sum. Point update: update the leaf, then update all ancestors. Range update with lazy propagation: instead of updating all affected leaf nodes, mark the update as pending on internal nodes (lazy tag). Propagate the tag down only when the node is accessed. This keeps range updates at O(log n) instead of O(n). Use segment trees for: range sum/min/max queries, count of elements in a range, any range aggregate with updates.
Fenwick Tree (Binary Indexed Tree)
A Fenwick tree (BIT) supports prefix sum queries and point updates in O(log n) with simpler code than a segment tree. It cannot do range minimum/maximum (only sum). Update(i, delta): add delta to position i. Update the BIT: while i 0: sum += bit[i]; i -= i & (-i) (remove the lowest set bit). Range sum [l, r] = query(r) – query(l-1). Use Fenwick tree for: count inversions, rank queries, prefix sums with updates. Simpler and faster constant than segment tree when only prefix sums are needed.
Trie Operations and Variants
Standard Trie: insert, search, starts_with in O(L) where L = word length. Space: O(total characters). TrieNode has children[26] and is_end flag. Deletion: mark is_end=False. Optionally, prune leaf nodes that are no longer words (check if all children are null). Word Search II (find all words on a board): build a Trie of all target words. DFS on the board — at each cell, follow the Trie pointer for the current letter. If no matching child: prune (do not recurse). If is_end: found a word. This is O(M * 4 * 3^(L-1)) where M = cells, L = max word length — much better than running separate DFS for each word. Compressed Trie (Patricia Trie): merge single-child nodes to save space and speed up queries on sparse tries.
BST Validation and Recovery
Validate BST: use in-order traversal. In a valid BST, in-order traversal produces a strictly increasing sequence. Track the previous node value — if current <= previous, return False. O(n) time, O(h) space. Alternative: pass valid range [min, max] to each recursive call. Root has range (-inf, +inf). Left child has range (min, root.val). Right child has range (root.val, max). Recover BST with two swapped nodes: in-order traversal, find two violations (where current < previous). The first violation's first node and the last violation's second node are the swapped nodes. Swap their values. O(n) time. Morris traversal enables O(1) space BST validation and recovery without explicit stack or recursion.
Lowest Common Ancestor with Binary Lifting
For multiple LCA queries on a static tree: binary lifting preprocesses in O(n log n) and answers each query in O(log n). Precompute: ancestor[v][k] = the 2^k-th ancestor of v (starting from parent, grandparent, …). Fill by: ancestor[v][0] = parent[v]. ancestor[v][k] = ancestor[ancestor[v][k-1]][k-1]. For LCA query (u, v): bring both nodes to the same depth by lifting the deeper node. Then lift both simultaneously until they meet. The meeting point is the LCA. Binary lifting is useful when thousands of LCA queries are needed on the same tree (static).
Interview Tips
- Segment trees vs Fenwick trees: if the problem needs range min/max or range updates, use a segment tree. If only prefix sum with point updates, use a Fenwick tree (simpler code, smaller constant).
- For Trie problems, the TrieNode class is always the same — define it first, then build operations on top. It rarely changes between problems.
- BST in-order = sorted. This observation solves: kth smallest, validate BST, and convert sorted list to BST.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide