Trees and Binary Search: Interview Pattern Guide

Why Trees and Binary Search Dominate Interviews

Trees and binary search appear in roughly 30-40% of coding interview rounds at major tech companies. There's a reason: they test recursive thinking, edge case awareness, and the ability to reason about structure — all things that correlate with strong engineering. Trees are inherently recursive data structures, which means solving tree problems forces you to think in terms of subproblems. Binary search, meanwhile, tests whether you can identify and maintain invariants under pressure.

The good news is that tree problems cluster into a small number of patterns. Once you internalize the four traversal orders and a handful of recursive templates, most tree problems become variations on a theme. Binary search is even more concentrated — the core idea is always the same, but the application context changes. This guide gives you the templates and the reasoning behind them so you can adapt to whatever variation shows up in your interview.

If you haven't already, read the 15 Coding Interview Patterns guide first. Trees draw heavily on the DFS and BFS patterns covered there, and binary search is pattern #11. This chapter goes deeper on both.

Tree Traversals: The Four Orders

Every tree problem starts with traversal — visiting nodes in a specific order. There are four traversal orders, and each one is useful for different categories of problems. Knowing which traversal to use is often the key insight that unlocks the solution.

The recursive implementations are straightforward. Here's the template that covers all three depth-first traversals — the only difference is where you process the current node:

def inorder(node):
  if not node: return
  inorder(node.left)
  process(node)  # inorder: between left and right
  inorder(node.right)

def preorder(node):
  if not node: return
  process(node)  # preorder: before children
  preorder(node.left)
  preorder(node.right)

def postorder(node):
  if not node: return
  postorder(node.left)
  postorder(node.right)
  process(node)  # postorder: after children

For level-order traversal, the template uses a queue and processes nodes level by level:

def level_order(root):
  if not root: return []
  queue = deque([root])
  result = []
  while queue:
    level_size = len(queue)
    level = []
    for _ in range(level_size):
      node = queue.popleft()
      level.append(node.val)
      if node.left: queue.append(node.left)
      if node.right: queue.append(node.right)
    result.append(level)
  return result

The critical detail in level-order traversal is capturing level_size before the inner loop. Without it, you lose the level boundaries and can't distinguish which nodes belong to which level. This is the single most common implementation mistake in BFS tree problems.

Iterative Inorder: The Stack-Based Approach

Interviewers sometimes ask for iterative traversals explicitly, or the problem structure makes recursion awkward (like the BST iterator problem). The iterative inorder uses an explicit stack and a pointer:

def inorder_iterative(root):
  stack, current = [], root
  result = []
  while stack or current:
    while current:
      stack.append(current)
      current = current.left
    current = stack.pop()
    result.append(current.val)
    current = current.right
  return result

The inner while current loop pushes all left children onto the stack. When it terminates, we pop and process (this is the "visit" step of inorder), then move to the right child. This template is the foundation for BST iterator, kth smallest element, and any problem that needs to process BST nodes in sorted order one at a time.

BST Properties and Operations

A binary search tree has one defining property: for every node, all values in its left subtree are strictly less than the node's value, and all values in its right subtree are strictly greater. This invariant gives you O(log n) search, insert, and delete on balanced trees — and it's the property that makes inorder traversal produce sorted output.

BST validation is a classic interview problem that tests whether you understand the property correctly. The naive approach — checking that each node is greater than its left child and less than its right child — is wrong. Consider a tree where the root is 10, left child is 5, and the left child's right child is 15. The naive check passes at every node, but 15 is in the left subtree of 10, violating the BST property.

The correct approach passes valid range bounds down the recursion:

def is_valid_bst(node, min_val=float('-inf'), max_val=float('inf')):
  if not node: return True
  if node.val <= min_val or node.val >= max_val:
    return False
  return (is_valid_bst(node.left, min_val, node.val) and
          is_valid_bst(node.right, node.val, max_val))

An alternative is inorder traversal validation: perform an inorder traversal and check that the output is strictly increasing. This works because inorder on a valid BST always produces sorted output. Both approaches are O(n) time, but the range-based approach short-circuits on the first violation.

BST search is straightforward: compare the target to the current node and go left or right accordingly. BST insertion follows the same path and attaches the new node at the first null position. BST deletion has three cases: leaf node (remove it), one child (replace with child), two children (replace with inorder successor or predecessor, then delete the successor). Deletion is the most complex and occasionally appears as an interview question, though it's less common than traversal and validation problems.

Recursive vs Iterative: When to Choose Which

A question that trips up many candidates: should I solve this recursively or iteratively? The answer depends on the problem structure and the interview context.

Default to recursion for tree problems. Trees are recursive structures, and recursive solutions are almost always cleaner and easier to reason about. The recursive template — base case, recursive calls on children, combine results — maps directly onto tree structure. Most interviewers prefer seeing a clean recursive solution over a convoluted iterative one.

Switch to iterative in three situations. First, when the problem explicitly asks for it (BST iterator, for example). Second, when you need to process nodes in a custom order that doesn't map cleanly to the standard traversals. Third, when stack depth could be an issue — a tree with 100,000 nodes and a worst-case linear shape will overflow the call stack in most languages. In practice, interviewers rarely test this edge case, but mentioning it shows awareness.

A strong interview technique: implement the recursive solution first, verify it works, then mention that you could convert to iterative if stack depth were a concern. This demonstrates both fluency with recursion and awareness of its limitations — without wasting time on a harder implementation unless asked.

The conversion from recursive to iterative DFS is mechanical: replace the call stack with an explicit stack, and replace recursive calls with stack pushes. For BFS, there is no recursive equivalent that's natural — always use a queue.

Path Problems and Ancestor Problems

Two categories of tree problems appear frequently enough to deserve their own section: path problems (finding or computing along root-to-leaf or node-to-node paths) and ancestor problems (finding relationships between nodes in a tree).

Path Sum Variants

The simplest version: given a target sum, determine if any root-to-leaf path sums to it. The recursive solution subtracts the current node's value from the target and recurses on children. At a leaf, check if the remaining target equals the leaf's value.

def has_path_sum(node, target):
  if not node: return False
  if not node.left and not node.right:
    return node.val == target
  return (has_path_sum(node.left, target - node.val) or
          has_path_sum(node.right, target - node.val))

The harder variant asks for all root-to-leaf paths that sum to the target. Same approach, but maintain a running path list and collect valid paths. Even harder: Path Sum III, where the path can start and end at any node. That one requires a prefix-sum approach — maintain a hash map of cumulative sums from the root, and at each node check if current_sum - target exists in the map. This is a combination of tree DFS and the prefix-sum pattern, and it's worth practicing until the combination feels natural.

Maximum Path Sum

This is one of the hardest tree problems you'll encounter in interviews: find the path with the maximum sum, where a path can go through any nodes (not just root-to-leaf, and it can bend at a node). The key insight is that at each node, you compute two things: the maximum path sum through this node (which could include both children — this is a candidate for the global answer) and the maximum path sum from this node going downward (which can only include one child — this is what you return to the parent).

def max_path_sum(root):
  result = [float('-inf')]
  def helper(node):
    if not node: return 0
    left = max(helper(node.left), 0)
    right = max(helper(node.right), 0)
    result[0] = max(result[0], left + node.val + right)
    return node.val + max(left, right)
  helper(root)
  return result[0]

The max(..., 0) call is critical — it handles the case where a subtree's contribution is negative, in which case you're better off not including it. This problem demonstrates the general pattern for tree problems where the answer isn't at the root: use a global variable (or mutable container) updated during traversal, while the recursion returns something different from the final answer.

Lowest Common Ancestor (LCA)

LCA is a recurring problem that shows up in variations across companies. Given two nodes p and q, find their lowest common ancestor — the deepest node that is an ancestor of both.

For a general binary tree, the elegant recursive solution is:

def lowest_common_ancestor(root, p, q):
  if not root or root == p or root == q:
    return root
  left = lowest_common_ancestor(root.left, p, q)
  right = lowest_common_ancestor(root.right, p, q)
  if left and right: return root
  return left if left else right

This works because if both left and right recursive calls return non-null values, the current node is where the paths to p and q diverge — that's the LCA. If only one side returns non-null, both p and q are on that side, so the result propagates upward. This is O(n) time and O(h) space where h is the tree height.

For a BST, you can do better. Since the BST property tells you which subtree contains each node, you can navigate directly: if both p and q are smaller than the current node, go left. If both are larger, go right. Otherwise, you've found the split point — that's the LCA. This runs in O(h) time and can be done iteratively.

LCA comes up in variations: LCA with parent pointers (convert to an intersection-of-two-linked-lists problem), LCA of multiple nodes, and LCA in an n-ary tree. The core recursive pattern adapts to all of these.

Binary Search Variations

Standard binary search — find a target in a sorted array — is something most engineers can write. What separates strong candidates is the ability to apply binary search to non-obvious situations. There are three major categories.

Category 1: Sorted Array Variations

These modify the standard binary search to handle complications in the input. Search in Rotated Sorted Array: at each step, determine which half is sorted (compare nums[mid] to nums[left]), check if the target falls in the sorted half, and eliminate accordingly. Find Minimum in Rotated Sorted Array: compare nums[mid] to nums[right] — if mid is greater, the minimum is in the right half. Search a 2D Matrix: treat the matrix as a flat sorted array and compute row/column from the flat index.

Category 2: Boundary Finding (Bisect Left / Bisect Right)

This is the most important binary search variation for interviews. Instead of finding the exact target, you find the insertion point — the first position where a value could be inserted to maintain sorted order.

Bisect left finds the leftmost position where the target could be inserted (i.e., the first element that is greater than or equal to the target):

def bisect_left(arr, target):
  lo, hi = 0, len(arr)
  while lo < hi:
    mid = (lo + hi) // 2
    if arr[mid] < target:
      lo = mid + 1
    else:
      hi = mid
  return lo

Bisect right finds the rightmost insertion point (first element strictly greater than the target):

def bisect_right(arr, target):
  lo, hi = 0, len(arr)
  while lo < hi:
    mid = (lo + hi) // 2
    if arr[mid] <= target:
      lo = mid + 1
    else:
      hi = mid
  return lo

The difference is one character: < vs <= in the comparison. This subtlety is the source of most binary search bugs. With bisect left, you can find the first occurrence of a value. With bisect right, you can find the last occurrence (it's at bisect_right - 1). Together, they solve Find First and Last Position of Element in Sorted Array.

Category 3: Binary Search on Answer Space

This is the most powerful and least intuitive application. Instead of searching an array, you search over the space of possible answers. The idea: if you can write a function feasible(x) that returns true for all x above some threshold and false below (or vice versa), you can binary search for that threshold.

Worked example: Koko Eating Bananas. Koko has piles of bananas and h hours. She eats at speed k bananas per hour (one pile at a time). What's the minimum k such that she finishes all piles within h hours?

The answer space is [1, max(piles)]. For a given k, you can compute the hours needed: sum(ceil(pile / k) for pile in piles). If hours <= h, k is feasible. Binary search for the smallest feasible k:

def min_eating_speed(piles, h):
  lo, hi = 1, max(piles)
  while lo < hi:
    mid = (lo + hi) // 2
    hours = sum((pile + mid - 1) // mid for pile in piles)
    if hours <= h:
      hi = mid
    else:
      lo = mid + 1
  return lo

This pattern applies to a wide range of problems: minimum capacity to ship packages within d days, maximum minimum distance between stalls, split array largest sum. The pattern is always the same: define the answer space, write the feasibility check, binary search. Once you recognize it, these problems become formulaic.

Worked Examples

Let's walk through five problems that combine the patterns above, with the kind of verbal reasoning you'd use in an interview.

Example 1: Validate Binary Search Tree

"I need to check that every node satisfies the BST property — not just relative to its parent, but relative to all ancestors. So I'll pass down valid bounds. The root can be anything, so I start with negative and positive infinity. When I go left, I update the upper bound to the current node's value. When I go right, I update the lower bound. At each node, if the value falls outside the bounds, it's invalid." This produces the range-based validation solution we covered earlier. Time: O(n). Space: O(h).

Example 2: Binary Tree Right Side View

"If I imagine looking at the tree from the right side, I'd see the last node at each level. That's a level-order traversal problem — I process each level and take the last node. Alternatively, I could do a modified preorder traversal that visits right before left, and the first node I see at each depth is the rightmost." The BFS approach is safer in an interview because it's harder to get wrong. Process levels left to right, record the last value in each level.

Example 3: Kth Smallest Element in a BST

"Inorder traversal of a BST gives sorted order. So I just need the kth element in an inorder traversal. I can do this recursively, but iterative inorder with a counter is more efficient — I can stop as soon as I've seen k elements instead of traversing the entire tree." Use the iterative inorder template. Each time you pop from the stack, decrement k. When k hits zero, that's your answer. Time: O(h + k). Space: O(h).

Example 4: First Bad Version

"I have versions 1 to n, and there's a cutoff point where all versions after it are bad. This is a bisect-left problem — I'm searching for the first position where isBadVersion returns true. The answer space is [1, n]. If mid is bad, the first bad version is at mid or earlier, so hi = mid. If mid is good, the first bad version is after mid, so lo = mid + 1." This is binary search on a boolean predicate. Time: O(log n). Space: O(1).

Example 5: Serialize and Deserialize Binary Tree

"I'll use preorder traversal for serialization because the root comes first, which gives me a natural starting point for deserialization. I'll represent null children as a sentinel value like '#'. For serialization, I do a preorder traversal and record each node's value, using '#' for null nodes. For deserialization, I consume values from the serialized list: each value becomes a node, then I recursively build its left and right subtrees. The '#' values terminate the recursion." This is one of the few problems where preorder is the natural choice. The key insight is that preorder with null markers uniquely determines the tree structure. Time: O(n) for both operations.

Common Mistakes and How to Avoid Them

After reviewing hundreds of interview performances on tree and binary search problems, these are the errors that come up most often:

Forgetting the base case in tree recursion. Every tree recursive function must handle the null node case. Forgetting it causes null pointer exceptions that waste precious debugging time. Write if not node: return ... as the first line of every recursive tree function, before you write anything else.

Off-by-one errors in binary search. The difference between lo < hi and lo <= hi, between hi = mid and hi = mid - 1, between using < and <= in the comparison — these subtle differences determine whether your binary search works, infinite-loops, or returns the wrong index. Pick one template (the bisect-left template above is the most versatile) and use it consistently. Don't improvise binary search from scratch each time.

Confusing node values with node references in LCA. In LCA problems, you're comparing node references (or node identity), not values. Two nodes with the same value are not the same node. Always compare with == on the node object, not on node.val.

Not handling the single-child case in BST operations. BST deletion with two children requires finding the inorder successor, but candidates sometimes forget the cases where the node has zero or one child. Handle the simpler cases first — they're easy points you shouldn't drop.

Using BFS when DFS is simpler, and vice versa. Level-order problems need BFS. Path problems need DFS. Diameter and height problems need postorder DFS. Matching the traversal to the problem structure is the first decision you should make, and getting it wrong means rewriting your solution from scratch.

Integer overflow in binary search midpoint calculation. In languages like Java and C++, (lo + hi) / 2 can overflow. Use lo + (hi - lo) / 2 instead. Python doesn't have this issue, but mentioning it in an interview shows awareness. Interviewers notice.

Trees and binary search are patterns you'll use throughout your career, not just in interviews. The recursive thinking that trees develop and the invariant-based reasoning that binary search requires are foundational engineering skills. If you want to pressure-test these patterns under realistic interview conditions, Hoppers AI's coding mock interviews let you practice with real-time feedback on your approach and implementation — a useful complement to solo practice. For more algorithmic patterns, continue with our guides on graph algorithms and dynamic programming.