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

Source: https://www.techinterview.org/post/3233463219/tree-interview-patterns/
Updated: 2026-04-17 · techinterview.org

## 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](https://techinterview.org/coinbase-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-software-engineer-interview/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-software-engineer-interview/)

- [Apple Interview Guide](https://techinterview.org/apple-software-engineer-interview/)

- [Meta Interview Guide](https://techinterview.org/meta-software-engineer-interview/)

## 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.