Part 3 of 6. Trees, BST and Heaps — the data structures that separate good programmers from great ones. Tree recursion is the single most testable skill in FAANG interviews. Master this part and your interview pass rate doubles.
Assume your function already works for the left and right subtrees. Given those results, what do you do at the current node? That's tree recursion in one sentence. Every tree problem follows: base case (null = 0 or false or empty) → recurse left → recurse right → combine at current node. The art is knowing what to return upward and what to track globally.
Return the maximum depth (number of nodes along longest root-to-leaf path) of a binary tree.
3
/ \
9 20
/ \
15 73Trust the recursion: assume maxDepth(left) and maxDepth(right) return correct depths. The current node adds 1 level. Base case: null node = depth 0.
Invert (mirror) a binary tree. Return the root of the inverted tree.
4
/ \
2 7
/\ /\
1 3 6 9 4
/ \
7 2
/\ /\
9 6 3 1At each node: swap its left and right children. Then recursively invert the left subtree and the right subtree. Base case: null node → return null. This is three lines of code — any more and you're overthinking it.
Same Tree: Are two trees structurally identical with same node values?
Symmetric Tree: Is a single tree a mirror of itself around its centre?
For Same Tree: both null → true. One null → false. Values differ → false. Else recurse both children.
For Symmetric: helper isMirror(left, right). Both null → true. One null → false. Values equal AND isMirror(left.left, right.right) AND isMirror(left.right, right.left).
Return all node values level by level (left to right) as a vector of vectors.
Use a queue. At the start of each level, snapshot the queue size. Process exactly that many nodes (one full level). Push their children. Repeat. The size snapshot prevents mixing levels.
Return true if the tree has a root-to-leaf path whose node values sum to targetSum.
target=22
5→[4→[11→[7,2]],
8→[13,4→[,1]]]true (5+4+11+2)At each node: subtract its value from the target. At a leaf: check if remaining == 0. Pass the reduced target down. This is cleaner than accumulating a sum because you don't need to check if you're at a leaf separately when summing.
Find the diameter of a binary tree — the longest path between any two nodes (may not pass through root). Return the number of edges.
1
/ \
2 3
/\
4 53[4,2,1,3]
or [5,2,1,3]The longest path through any node uses the tallest path in its left subtree PLUS the tallest path in its right subtree. DFS returns height upward while updating a global maximum with (left_height + right_height) at each node. These are two different things — the return value (height) and the side-effect (update max diameter).
Find the maximum path sum in a binary tree. A path is any sequence of nodes where each pair of adjacent nodes has an edge. The path does not need to pass through the root. Nodes can be negative.
[-10,9,20,null,null,15,7]42 (15+20+7)What to update globally: node.val + max(0, leftGain) + max(0, rightGain). This is the max path that passes through this node as the "peak".
What to return upward: node.val + max(0, max(leftGain, rightGain)). You can only continue the path through ONE branch going upward — you can't split.
Clamp negative gains to 0: a negative subtree only hurts, so don't include it.
Find the Lowest Common Ancestor (LCA) of two nodes p and q in a binary tree (not necessarily a BST).
root=[3,5,1,6,2,0,8]
p=5, q=13p=5, q=45If the current node is p or q, return it. Recurse left and right. If both return non-null → p and q are in different subtrees → current node is the LCA. If only one returns non-null → both are in that subtree → propagate the found node upward.
Return the values of the nodes visible when standing to the right of the tree (rightmost node of each level).
1
/ \
2 3
\ \
5 4[1,3,4]Level-order BFS (see Q074). At the end of processing each level, the last node processed is the rightmost visible node. Push it to result. Can also do DFS: visit right child first, and include only the first node encountered at each depth.
A "good node" is a node where no ancestor has a value greater than it. Count all good nodes.
DFS with an extra parameter: maxSoFar = the maximum value on the path from root to current node. A node is "good" if node.val >= maxSoFar. Update maxSoFar = max(maxSoFar, node.val) before recursing.
Check if a binary tree is height-balanced. A tree is balanced if for every node, the heights of left and right subtrees differ by at most 1.
The naive approach calls height() for every node — O(n²). Better: DFS returns height, but returns -1 if ANY subtree is unbalanced. Once -1 propagates up, all ancestors short-circuit. Total: O(n).
Construct a binary tree from its preorder and inorder traversal arrays.
[3,9,20,15,7][9,3,15,20,7] 3
/ \
9 20
/\
15 7Preorder's first element is always the root. Find it in inorder — everything to its left is the left subtree, everything to its right is the right subtree. Count tells you how many preorder elements belong to each subtree. Recurse. Use a hash map for O(1) inorder lookups.
Design an algorithm to serialize a binary tree to a string and deserialize it back. The encoded string must be decodable to the original tree structure.
Preorder DFS: write node values with a separator. Write "N" for nulls. This uniquely determines the structure because the null markers tell us exactly where subtrees end. Deserialize by reading tokens in preorder and recursively building.
Each root-to-leaf path forms a number (e.g. path 1→2→3 = 123). Sum all such numbers.
4
/ \
9 0
/\
5 11026495+491+40=1026Level-order traversal but alternate left-to-right and right-to-left per level.
Flatten a binary tree in-place to a linked list in preorder. Use right pointers, set all left pointers to null.
1/[2/[3,4],5/[,6]]1→2→3→4→5→6 (right ptrs)For each node with a left child: find the rightmost node of the left subtree (it's the predecessor in preorder). Connect the right subtree to that node's right. Move the left subtree to be the right child. Set left to null. Advance to right child and repeat.
Count paths in a binary tree that sum to a target. The path must go downward but doesn't need to start or end at root/leaf.
Same as subarray sum equals k (Q021) but on a tree path. DFS with a hash map storing prefix sums. At each node: check if (currentSum - target) exists in the map → that many paths end here. Add currentSum to map, recurse, then remove it (backtrack). O(n) instead of O(n²).
Place the minimum number of cameras on tree nodes. Each camera monitors its node, parent, and immediate children. Return the minimum cameras needed to monitor all nodes.
Bottom-up DFS with three states: 0 = uncovered (needs a camera from parent), 1 = has camera, 2 = covered (by child camera). Leaves return 0. A node places a camera if any child is uncovered (state 0). If any child has a camera, this node is covered (state 2). Otherwise state 0. Root: if root is state 0, add one more camera.
Property: left < node < right at every node. This is a global constraint, not just parent-child.
Inorder traversal of BST = sorted array. This is the single most useful BST fact. Any problem asking "k-th smallest", "sorted output", or "predecessor/successor" uses inorder.
Search, insert, delete: O(h) = O(log n) balanced, O(n) skewed. Always ask if the tree is balanced.
BST vs Binary Tree: In BST problems, USE the BST property to prune. If you're traversing every node, you're ignoring the BST structure.
Find and return the subtree rooted at the node with value equal to the target. Return null if not found.
Given a binary tree, determine if it is a valid BST.
The value at each node must satisfy the constraints of ALL its ancestors, not just its direct parent. Pass a (lo, hi) range down the tree. Going left: hi = parent's value. Going right: lo = parent's value. A node is valid only if lo < node.val < hi.
Find the kth smallest element in a BST in O(h+k) time.
Inorder traversal of a BST visits nodes in ascending order. The kth node visited in inorder is the kth smallest. Use iterative inorder with an explicit stack to stop early at exactly k nodes — no need to traverse the whole tree.
Find LCA of p and q in a BST. Unlike a general binary tree, use the BST property to guide the search.
If both p and q are smaller than the current node, the LCA must be in the left subtree. If both are larger, the LCA is in the right subtree. Otherwise, the current node is where they diverge — it IS the LCA. O(h) — no need to explore both subtrees.
Insert: Insert a value into a BST, return the new root.
Delete: Delete a node with given key from a BST. Three cases to handle.
Case 1: Leaf node → just delete (return null).
Case 2: One child → replace with that child.
Case 3: Two children → replace value with inorder successor (smallest in right subtree), then delete the successor from right subtree.
Convert a sorted array to a height-balanced BST.
Implement a BST iterator with next() returning next smallest and hasNext(). Both must run in O(1) average with O(h) space.
Maintain an explicit stack. Constructor: push all leftmost nodes from root. next(): pop the top (that's the next smallest), then push all leftmost nodes of its right subtree. This is "paused inorder" — we only push nodes we'll visit next.
Exactly two nodes in a BST are swapped by mistake. Recover the tree by fixing the two nodes without changing structure.
In inorder traversal of a valid BST, values are strictly increasing. The two swapped nodes create descents (where prev > current). There are either one or two descents. The first node to swap = first.prev at the first descent. The second = second.current at the last descent. Swap their values.
Count the number of structurally unique BSTs that can store values 1 to n.
Output: 5Output: 1If we pick i as the root, the left subtree has (i-1) nodes and the right has (n-i) nodes. The number of combinations = G(i-1) × G(n-i). Sum over all root choices. This is the Catalan number recurrence: G(0)=G(1)=1.
Signal 1 — "Kth largest/smallest": Min-heap of size k. If new element > top: pop, push. Final top = kth largest.
Signal 2 — "Stream of numbers": Two heaps (max + min) for running median. Min-heap for running minimum.
Signal 3 — "Merge k sorted": Push head of each list. Pop min, push next from same list. O(n log k).
Signal 4 — "Scheduling/Tasks": Priority queue ordered by deadline, frequency, or cost.
Signal 5 — Greedy + Ordering: Always processing the most/least extreme element? Heap is your structure.
Find the kth largest element in an unsorted array. Not the kth distinct element.
[3,2,1,5,6,4], k=25A min-heap of size k tracks the k largest elements. The heap top is the kth largest (the minimum of the k largest). For each new element: push it. If heap size exceeds k, pop the minimum. At the end, heap.top() = kth largest.
Design a structure supporting addNum(int) and findMedian(). addNum runs in O(log n), findMedian in O(1).
Two heaps partition the sorted array. maxH (lower half): max-heap, top = largest of the smaller half. minH (upper half): min-heap, top = smallest of the larger half. Keep them balanced: |size difference| ≤ 1. Median = top of larger heap (odd) or average of both tops (even).
Merge k sorted linked lists into one sorted list. (Revisited here from heap perspective.)
n total nodes, k lists. Each node enters the heap once (O(log k)) and exits once (O(log k)). Total: O(n log k). Space: O(k) for the heap. Compare with naive pairwise merge: O(n log k) same time but O(1) space if done carefully.
Return the k closest points to the origin (0,0). Distance = sqrt(x²+y²) — but compare x²+y² to avoid sqrt.
pts=[[1,3],[-2,2]]
k=1[[-2,2]]Use a max-heap by distance. Keep at most k elements. When a new point has distance less than the farthest in the heap (the max-heap top), pop the farthest and push the new point. Final heap contains the k closest.
Return the k most frequent words from a list. If tie in frequency, sort alphabetically.
["i","love","leetcode","i",
"love","coding"], k=2["i","love"]Find the nth ugly number. Ugly numbers have only prime factors 2, 3, 5. Sequence: 1,2,3,4,5,6,8,9,10,12...
Start with 1 in a min-heap. Each time you pop a number x, push x×2, x×3, x×5. Use a set to avoid duplicates. The nth pop is the nth ugly number.
You have initial capital W and can complete k projects. Project i needs capital[i] to start and gives profit[i]. Maximize final capital.
Sort projects by capital. Use a min-heap of (capital, profit). Use a max-heap of profit. Greedy: For each of k rounds, add all affordable projects (capital ≤ W) to max-heap. Pick the most profitable (max-heap top). Add its profit to W. If no project is affordable and max-heap is empty, stop.
Connect sticks with minimum total cost. Each connection costs the sum of two sticks' lengths. Find the minimum total cost to connect all sticks into one.
[2,4,3]142+3=5(cost5)
5+4=9(cost9)
total=14This is exactly Huffman coding. If you merge large sticks early, that cost propagates into all future merges. Merging the two smallest first minimizes total accumulated cost. Min-heap: repeatedly pop two smallest, push their sum, add sum to total cost.