Binary Tree Problems — 10 Patterns for Coding Interviews

Binary tree problems aren't about trees. They're about recursion patterns. Once you internalize the 10 patterns below, every new tree question becomes "which template does this match?" instead of starting from scratch.

The reason people struggle with tree questions: they try to think iteratively about a recursive structure. Trees are recursion's natural habitat. Lean into it.

Pattern 1: DFS Traversals (Preorder, Inorder, Postorder)

Every tree problem uses one of these traversal orders. The question is which one fits your problem.

• Preorder (root → left → right): when you need to process the current node before its children. Copying a tree, serialization.
• Inorder (left → root → right): BSTs. Inorder traversal of a BST gives sorted order.
• Postorder (left → right → root): when you need children's results before processing the parent. Height calculation, deletion.

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

function preorder(root) {
  if (!root) return [];
  return [root.val, ...preorder(root.left), ...preorder(root.right)];
}

function inorder(root) {
  if (!root) return [];
  return [...inorder(root.left), root.val, ...inorder(root.right)];
}

function postorder(root) {
  if (!root) return [];
  return [...postorder(root.left), ...postorder(root.right), root.val];
}

These are educational implementations. In practice you'd pass a result list by reference instead of creating new arrays at every call.

Pattern 2: BFS (Level-Order Traversal)

Use a queue. Process all nodes at depth d before moving to depth d+1. Critical for "level by level" problems — zigzag traversal, right-side view, level averages.

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            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

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length > 0) {
    const level = [];
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

The for _ in range(len(queue)) trick processes exactly one level per outer loop iteration. Without it, you'd mix levels together.

Pattern 3: Height / Depth Calculation

Postorder pattern. You need children's heights before you can compute the parent's height.

def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

function height(root) {
  if (!root) return 0;
  return 1 + Math.max(height(root.left), height(root.right));
}

This is the building block for balanced tree checks, diameter calculation, and more. If you're computing height from the top down, you're doing it wrong.

Pattern 4: Diameter of Binary Tree

The diameter is the longest path between any two nodes (measured in edges). It doesn't have to pass through the root.

At each node, the longest path through that node is left_height + right_height. Track the global maximum.

def diameter(root):
    best = [0]

def height(node):
        if not node:
            return 0
        l = height(node.left)
        r = height(node.right)
        best[0] = max(best[0], l + r)
        return 1 + max(l, r)

height(root)
    return best[0]

function diameter(root) {
  let best = 0;

function height(node) {
    if (!node) return 0;
    const l = height(node.left);
    const r = height(node.right);
    best = Math.max(best, l + r);
    return 1 + Math.max(l, r);
  }

height(root);
  return best;
}

The trick: you compute height (return value) but you use both heights to update a separate metric (diameter). This "compute one thing, track another" pattern repeats constantly.

Pattern 5: Path Sum Problems

Three flavors, escalating difficulty:

Has path sum (root to leaf):

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

All paths with given sum — same structure, but collect paths:

def path_sum_all(root, target):
    result = []

def dfs(node, remaining, path):
        if not node:
            return
        path.append(node.val)
        if not node.left and not node.right and remaining == node.val:
            result.append(list(path))
        dfs(node.left, remaining - node.val, path)
        dfs(node.right, remaining - node.val, path)
        path.pop()  # backtrack

dfs(root, target, [])
    return result

Path sum from any node to any descendant — prefix sum technique on tree paths. That's a different beast and uses Pattern 9 below.

Pattern 6: Lowest Common Ancestor (LCA)

For a regular binary tree (not BST): if p and q are in different subtrees, the current node is the LCA. If both are in the same subtree, recurse into that subtree.

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

function lca(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lca(root.left, p, q);
  const right = lca(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

Five lines. Runs in O(n). This is one of those algorithms where the code is shorter than the explanation.

For BSTs, you can do better — if both values are less than root, go left. If both are greater, go right. Otherwise, root is the LCA.

Pattern 7: Tree Construction

Build a tree from traversal arrays. The classic: construct from preorder + inorder.

Preorder's first element is the root. Find it in inorder — everything to its left is the left subtree, everything right is the right subtree. Recurse.

def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None

root = TreeNode(preorder[0])
    mid = inorder.index(preorder[0])

root.left = build_tree(preorder[1:mid + 1], inorder[:mid])
    root.right = build_tree(preorder[mid + 1:], inorder[mid + 1:])

return root

The O(n) optimization: build a hash map from value → index for the inorder array, and pass indices instead of slicing.

Pattern 8: Serialize / Deserialize

Convert a tree to a string and back. Preorder with null markers is the simplest approach.

def serialize(root):
    if not root:
        return "null"
    return f"{root.val},{serialize(root.left)},{serialize(root.right)}"

def deserialize(data):
    nodes = iter(data.split(","))

def build():
        val = next(nodes)
        if val == "null":
            return None
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node

return build()

function serialize(root) {
  if (!root) return "null";
  return ${root.val},${serialize(root.left)},${serialize(root.right)};
}

function deserialize(data) {
  const nodes = data.split(",")[Symbol.iterator]();

function build() {
    const { value } = nodes.next();
    if (value === "null") return null;
    const node = { val: parseInt(value), left: null, right: null };
    node.left = build();
    node.right = build();
    return node;
  }

return build();
}

Using an iterator avoids index-tracking headaches. The iterator advances naturally through the preorder sequence.

Pattern 9: Prefix Sum on Tree Paths

"Count paths that sum to target from any node to any descendant." This is path sum III (LeetCode 437). Apply the prefix sum idea from arrays, but on root-to-node paths.

def path_sum_iii(root, target):
    count = [0]
    prefix = {0: 1}

def dfs(node, running):
        if not node:
            return
        running += node.val
        count[0] += prefix.get(running - target, 0)
        prefix[running] = prefix.get(running, 0) + 1

dfs(node.left, running)
        dfs(node.right, running)

prefix[running] -= 1  # backtrack

dfs(root, 0)
    return count[0]

The backtracking step is what makes this work on trees instead of arrays — when you leave a subtree, you remove that path's contribution from the prefix map.

Pattern 10: Validate BST

The classic "is this a valid BST?" — not just left < root < right, but all left descendants < root < all right descendants.

Pass valid ranges down:

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

function isValidBST(root, lo = -Infinity, hi = Infinity) {
  if (!root) return true;
  if (root.val <= lo || root.val >= hi) return false;
  return isValidBST(root.left, lo, root.val) &&
         isValidBST(root.right, root.val, hi);
}

Alternative: inorder traversal should produce a strictly increasing sequence. If it doesn't, not a valid BST.

Complexity Summary

Pattern	Time	Space
DFS traversals	O(n)	O(h) stack
BFS level-order	O(n)	O(w) queue
Height / depth	O(n)	O(h)
Diameter	O(n)	O(h)
Path sum (root-to-leaf)	O(n)	O(h)
LCA	O(n)	O(h)
Construction	O(n) with hash map	O(n)
Serialize/Deserialize	O(n)	O(n)
Prefix sum paths	O(n)	O(n)
Validate BST	O(n)	O(h)

Where h = height of tree (O(log n) balanced, O(n) worst case), w = max width.

Common Mistakes

Confusing node values with node references in LCA. You're comparing nodes (pointers/references), not their values. Two nodes can have the same value. Off-by-one in BST validation. Using < instead of <= (or vice versa) depending on whether duplicates are allowed. Clarify with the interviewer. Forgetting to backtrack. Path collection and prefix sum problems require undoing your changes when you leave a subtree. Miss the path.pop() and your paths bleed across branches. Using BFS when DFS is simpler. Most tree problems are naturally recursive (DFS). Only reach for BFS when the problem is explicitly level-based.

These 10 patterns cover the vast majority of tree interview questions. Practice them individually on CodeUp until you can identify which pattern applies within 30 seconds of reading a problem.