Tree Interview Patterns: DFS, BFS, LCA, BST, Tree DP, Serialization

By /
⏱ 5 min read

Tree Interview Patterns

Trees appear in nearly every software engineering interview. Mastering the core traversal patterns and recognizing which technique applies is the key skill.

  • Coinbase Interview Guide
  • Uber Interview Guide
  • Atlassian Interview Guide
  • LinkedIn Interview Guide
  • Apple Interview Guide
  • Meta Interview Guide

    • Pattern 1: DFS Traversals

    Three orderings — preorder (root, left, right), inorder (left, root, right), postorder (left, right, root).

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

# Iterative inorder (important for interviews):
def inorder_iter(root):
    stack, result = [], []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur); cur = cur.left
        cur = stack.pop()
        result.append(cur.val)
        cur = cur.right
    return result

    BST inorder produces a sorted sequence — used to validate BST, find kth smallest.

    Pattern 2: BFS / Level Order

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

    Use BFS for: level-order traversal, min depth, zigzag traversal, connect next pointers.

    Pattern 3: Tree DP (Bottom-Up)

    Many tree problems require computing a value at each node based on its children. Classic: Diameter of Binary Tree.

    def diameter(root):
    best = [0]
    def height(node):
        if not node: return 0
        L, R = height(node.left), height(node.right)
        best[0] = max(best[0], L + R)  # path through this node
        return 1 + max(L, R)
    height(root)
    return best[0]

    Pattern: return something to parent (height/gain/value), update a global answer at each node. Used for: diameter, max path sum, camera placement, rob houses on tree.

    Pattern 4: Lowest Common Ancestor (LCA)

    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  # p and q on different sides
    return left or right

    For BST: if both p,q < root go left; if both > root go right; else root is LCA. O(log N) for balanced BST.

    Pattern 5: BST Operations

    • Search: O(h) — go left if val < root, right if val > root
    • Insert: same as search until null, then create node
    • Delete: (1) leaf: just remove; (2) one child: replace with child; (3) two children: replace with inorder successor (leftmost node in right subtree)
    • Validate BST: pass min/max bounds down. At each node: val must be in (min, max). Left subtree max = current val; right subtree min = current val.

    Pattern 6: Serialize / Deserialize

    def serialize(root):
    if not root: return 'N,'
    return str(root.val) + ',' + serialize(root.left) + serialize(root.right)

def deserialize(data):
    vals = iter(data.split(','))
    def build():
        v = next(vals)
        if v == 'N': return None
        node = TreeNode(int(v))
        node.left, node.right = build(), build()
        return node
    return build()

    Pattern 7: Path Problems

    • Path sum: DFS with remaining target; return True when leaf reached with target=0
    • All root-to-leaf paths: DFS with current path list; copy at leaf
    • Max path sum: Tree DP — at each node, max gain from left/right subtrees (take max with 0 to skip negative branches)

    Interview Tips

    • Always handle the null base case first.
    • Recursive DFS is clean for tree DP; iterative is needed if stack overflow is a concern (N=10^5).
    • For BST problems, use the sorted inorder property as the primary insight.
    • When the answer spans across two subtrees, track a global variable updated at each node.
    Scroll to Top