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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use a segment tree vs a Fenwick tree?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Fenwick tree (BIT): supports point updates and prefix sum queries in O(log n) with simpler code and smaller constant. Cannot do range minimum/maximum or range updates without significant modification. Use for: prefix sum queries, counting inversions, rank queries, when you only need sum aggregation. Segment tree: supports any associative aggregate (sum, min, max, GCD, XOR), range updates (with lazy propagation), and range queries. More versatile but more complex to implement. Use for: range minimum/maximum queries, range updates, problems requiring non-sum aggregates. Rule of thumb: if the problem only needs prefix sums or range sums with point updates, use a Fenwick tree (shorter code, easier to debug). For anything more complex — segment tree.”
}
},
{
“@type”: “Question”,
“name”: “How does lazy propagation work in a segment tree?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Without lazy propagation: a range update (add 5 to all elements in [l, r]) updates all O(n) leaf nodes. With lazy propagation: store pending updates on internal nodes. A lazy tag at a node means ‘all elements in this range need this update applied, but we haven’t propagated it yet.’ Update: if the node’s range is fully covered by [l, r]: apply the update to the node’s aggregate and store the lazy tag. Stop recursing. If partially covered: push down the lazy tag to children (propagate), then recurse. Query: push down lazy tags on the way down before reading children. This ensures queries see correct values even when updates are pending. Total complexity remains O(log n) per update or query. Lazy propagation transforms range updates from O(n) to O(log n).”
}
},
{
“@type”: “Question”,
“name”: “How do you use a Trie to solve the Word Search II problem efficiently?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Word Search II: given a grid of characters and a list of words, find all words in the grid. Naive approach: for each word, run DFS on the grid. O(words * grid_cells * 4^word_length). With Trie: build a Trie of all target words. Run one DFS over the grid, guided by the Trie. At each cell: if there is no Trie child for the current character, prune (do not recurse). If a Trie node has is_end=True: found a word, add to results. This prunes invalid paths early — if no word starts with ‘XQ’, the DFS stops immediately at an ‘X’ followed by ‘Q’. Optimization: after finding a word, remove it from the Trie (set is_end=False, prune childless nodes) to avoid redundant processing. The Trie DFS makes the algorithm dependent on the board size and shared prefixes rather than the total length of all words.”
}
},
{
“@type”: “Question”,
“name”: “How do you validate a Binary Search Tree efficiently?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Method 1 (range-based, O(n)): for each node, track the valid range (min_val, max_val). Root: (-inf, +inf). Left child of node with value v: (min_val, v). Right child: (v, max_val). At each node: if not min_val < node.val node.left.val) — this misses cases where a left subtree node is greater than an ancestor. Method 2 (in-order, O(n)): in-order traversal of a valid BST produces a strictly increasing sequence. Track the previous value; if current <= previous, invalid. Method 2 is easier to code correctly. Method 1 is slightly more elegant. Both are O(n) time, O(h) space (recursion stack)."
}
},
{
"@type": "Question",
"name": "What is the Morris traversal and when is O(1) space tree traversal needed?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Morris traversal achieves O(1) space in-order traversal by temporarily modifying the tree structure. The key observation: for any node with a left subtree, find the in-order predecessor (rightmost node in the left subtree). Make it point to the current node (threading). On revisit (following the thread): process the node and remove the thread. Algorithm: while current != None: if current.left is None: process current; current = current.right. Else: find rightmost in left subtree (predecessor). If predecessor.right is None: set predecessor.right = current (create thread); current = current.left. Else: remove thread; process current; current = current.right. Use Morris traversal when: space is severely constrained (embedded systems, competitive programming), or when solving BST problems requiring O(1) space (recover BST, validate BST, find kth smallest). Recursive approaches use O(h) stack space which can be O(n) for skewed trees."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide