1. Why Searching One-by-One Breaks Down
Linear search checks every element. It's simple but brutal. If you have 1,000,000 items, it takes 1,000,000 steps. Binary search exploits sorted order to eliminate half the search space every step. Watch the difference in operations below. Target: 72.
2. Binary Search on Answer: Koko Eating Bananas
Sometimes the search space isn't an array—it's a range of possible answers. Koko has h hours to eat n piles of bananas. If she eats k bananas per hour, what is the minimum k to finish in time? We binary search the "speed" (k). The isFeasible(k) function checks if a given speed works. Adjust the speed and run the simulation.
3. Tree Traversals: The Three Orders You Must Know
A Binary Tree is just nodes linked by edges. To process them, we use Depth-First Search (DFS). The order you visit nodes changes the use case: Inorder (Left, Root, Right) gives sorted data in a BST. Preorder (Root, Left, Right) is used to clone or serialize a tree. Postorder (Left, Right, Root) is used to delete a tree safely.
4. Level Order Traversal: The BFS That Catches Fraud
Instead of diving deep, Breadth-First Search (BFS) explores level by level. It uses a Queue (FIFO). When you process a node, you push its children to the back of the queue. This is critical in production for finding shortest paths in unweighted graphs, routing, and fraud detection (finding connected entities within N degrees).
5. The Diameter of a Binary Tree
The diameter is the longest path between any two nodes. It doesn't have to pass through the root! The O(n) trick is a post-order DFS: at every node, calculate the height of the left and right subtrees. The path through the current node is left_height + right_height. Track the maximum path seen, and return the height to the parent.
6. Search in Rotated Sorted Array
A sorted array has been rotated at an unknown pivot (e.g., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Standard binary search breaks because the halves aren't purely sorted. The trick: at every step, one half must be normally sorted. Find out which half it is, then decide if the target lies within that sorted range. Target: 0.
7. Serialize and Deserialize Binary Tree
To save a tree to disk or send it over a network, you must flatten it to a string. We use BFS (Level-Order) with null markers for missing children, creating the LeetCode format (e.g., [1,2,3,null,null,4,5]). Step through the serialization to see how the queue processes nulls to preserve the exact tree structure.
8. Morris Traversal: The O(1) Space Trick
Standard Inorder traversal uses O(N) space for the call stack or an explicit stack. Morris Traversal achieves it in O(1) space. It works by temporarily modifying the tree: when traversing left, it finds the inorder predecessor (rightmost node in the left subtree) and links it back to the current node. This "thread" allows the algorithm to return to the root without a stack. Once returned, the thread is cut, restoring the original tree.
9. The Fenwick Tree (BIT): Range Sum Magic
A Fenwick Tree achieves O(log n) range sum queries and point updates using an array. It relies on bitwise logic: index i stores the sum of a range of elements determined by the least significant set bit of i. To get a prefix sum, you jump backwards using i -= i & (-i). To update, you jump forwards using i += i & (-i). Let's calculate the Prefix Sum of index 7.
10. Binary Tree Basics: Structure & Properties
A binary tree is a hierarchical structure where each node has at most two children — left and right. Every node has a depth (distance from root) and a height (longest path to a leaf). Click any node to inspect its properties.
Height = longest path to a leaf.
Depth = distance from the root.
Leaf = node with no children.
Full tree: every node has 0 or 2 children.
Complete tree: all levels filled left-to-right.
11. Binary Search Tree: Insert & Search
A BST enforces left < node < right at every level. Both insert and search are O(h) — O(log n) when balanced, O(n) in a skewed tree. Watch how each comparison halves the remaining candidates.
12. Tree Height, Depth & Balance Factor
A tree is height-balanced if |height(left) − height(right)| ≤ 1 at every node. AVL trees enforce this. We compute height bottom-up via post-order traversal. Step through to see balance factors annotated on each node.
13. Lowest Common Ancestor (LCA)
The LCA of nodes A and B is the deepest node that is an ancestor of both. The elegant recursive solution: if root is null or equals A or B, return root. Otherwise recurse left and right — if both return non-null, the current node is the LCA. O(n) time, O(h) space.
14. BST → Sorted Array: The Inorder Property
Inorder traversal of a BST (left → root → right) always yields elements in sorted ascending order. This property lets you extract a sorted array in O(n) and reconstruct a balanced BST from a sorted array in O(n). Step through to watch the array build.
15. Segment Tree: Range Queries in O(log n)
A segment tree answers range sum (or min/max) queries in O(log n) with O(log n) point updates. Each node stores the aggregate of its subarray range. A query on [L,R] uses at most O(log n) nodes — it only visits nodes whose range overlaps [L,R].
16. Trie: Prefix Search in O(k)
A trie (prefix tree) stores strings character by character. Search and insert are O(k) where k = word length. The power: all words sharing a prefix share the same path from root. Pre-loaded: apple, app, apt, bad, bat.
17. AVL Tree: Self-Balancing via Rotations
AVL trees restore the balance factor (|BF| ≤ 1) after each insert via rotations. Four cases: LL (single right-rotate), RR (single left-rotate), LR (left-rotate child then right-rotate root), RL (right-rotate child then left-rotate root). Select a case and step through.
18. Ternary Search: Finding a Unimodal Peak
Ternary search finds the peak of a unimodal (bitonic) array by dividing it into thirds. Compare values at m1 = L + (R−L)/3 and m2 = R − (R−L)/3. Eliminate the third that can't contain the peak. O(log₃ n) — slightly slower than binary search for the same reason log₃ > log₂.
19. Jump Search: Block-by-Block
Jump search skips ahead in blocks of size √n until it finds a block that could contain the target, then does a linear scan backward through that block. O(√n) time — better than linear O(n) but needs a sorted array like binary search. Optimal block size is exactly √n.
20. Interpolation Search: Smart Probing
For uniformly distributed sorted data, interpolation search uses: pos = lo + (target−arr[lo]) × (hi−lo) / (arr[hi]−arr[lo]). It estimates where the target likely is, rather than always going to the midpoint. Average O(log log n) — but degrades to O(n) on skewed data.
21. Exponential Search: Doubling Bounds
Exponential search works on sorted arrays by first doubling the index (1 → 2 → 4 → 8…) until the value at that index exceeds the target, establishing a range. Then binary search runs within [prev, current]. O(log n) overall — ideal for unbounded or very large arrays where the target is near the beginning.
Interview Questions
The 12 most common search and tree questions in engineering interviews — from FAANG to mid-stage startups. Click any question to reveal the answer.
arr[mid] where mid = (lo + hi) / 2.height(left) − height(right) and must be in {-1, 0, 1}. AVL trees are more strictly balanced than Red-Black trees, so they offer faster lookups (shorter paths). Red-Black trees use a coloring invariant (no two consecutive red nodes, equal black-height on all paths) that allows slightly looser balance, resulting in fewer rotations on insert/delete. std::map in C++ and TreeMap in Java use Red-Black trees; AVL trees are preferred in read-heavy workloads.lo + (target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]) — it estimates where the target is based on value distribution rather than always halving. For uniformly distributed data, it achieves O(log log n) average case, beating binary search's O(log n). Worst case is O(n) for skewed distributions (e.g., exponentially growing values). It's most useful for large sorted numerical datasets with known uniform distribution — phone book lookups, sorted IP ranges.