# Tree Traversals — Part 1: The Pattern

Trees are where recursion feels most natural: a tree is a root plus two smaller trees. Almost every binary-tree interview problem is one of two traversals with a small twist: **depth-first search** (DFS: preorder, inorder, postorder), usually written recursively, or **breadth-first search** (BFS: level by level), written with a queue. The real skill is deciding **what each recursive call returns** and **what information flows down vs up**.

![Preorder, inorder and postorder visit orders on the same tree](diagrams/01-dfs-orders.svg)

## 1. The Node

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right
```

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}
```

LeetCode serializes trees in **level order with nulls**: `[3,9,20,null,null,15,7]` is a root 3 with children 9 and 20, and 20 has children 15 and 7.

## 2. The Four Orders

| Order | Visit | Typical use |
|---|---|---|
| **Preorder** | node → left → right | copy/serialize a tree, pass state **down** (path sums, depth) |
| **Inorder** | left → node → right | BST in **sorted order**, k-th smallest, validate BST |
| **Postorder** | left → right → node | compute from children **up** (height, diameter, subtree sums), delete a tree |
| **Level order (BFS)** | level by level | per-level answers (averages, right side view), shortest depth |

## 3. Templates

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function maxDepth(root: TreeNode | null): number {
  return root ? 1 + Math.max(maxDepth(root.left), maxDepth(root.right)) : 0;
}

function inorder(root: TreeNode | null): number[] {
  const out: number[] = [], stack: TreeNode[] = [];
  let node = root;
  while (stack.length || node) {
    while (node) { stack.push(node); node = node.left; }
    node = stack.pop()!;
    out.push(node.val);
    node = node.right;
  }
  return out;
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  let q: TreeNode[] = [root];
  while (q.length) {
    res.push(q.map((n) => n.val));
    q = q.flatMap((n) => [n.left, n.right].filter((c): c is TreeNode => c !== null));
  }
  return res;
}

function traversals(level: (number | null)[]): any[] {
  const root = _tree(level);
  return [maxDepth(root), inorder(root), levelOrder(root)];
}
```

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

from collections import deque

def max_depth(root):                         # bottom-up: children report, parent combines
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def inorder(root):                           # iterative DFS with an explicit stack
    out, stack, node = [], [], root
    while stack or node:
        while node:
            stack.append(node); node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

def level_order(root):                       # BFS, one level per loop iteration
    if not root:
        return []
    res, q = [], 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)
        res.append(level)
    return res

def traversals(level):
    root = _tree(level)
    return [max_depth(root), inorder(root), level_order(root)]
```

## 4. Top-Down vs Bottom-Up

- **Top-down (preorder):** pass information **down** as parameters: current depth, path sum so far, the allowed `(low, high)` range for BST validation. Answers are often collected in an outer variable at the leaves.
- **Bottom-up (postorder):** each call **returns** a summary of its subtree (height, sum, "is balanced"), and the parent combines its children's summaries.

Some problems need **both**: Diameter and Maximum Path Sum return the best *one-sided* path upward, while updating a global answer with the best *two-sided* path through the current node. Recognizing that split is the key insight interviewers look for.

## 5. Recursive vs Iterative

Recursion is shorter and clearer, but uses the call stack (O(h) for tree height h, which is O(n) for a skewed tree). Iterative DFS uses an explicit stack; iterative BFS uses a queue. Be ready to write the iterative inorder (the "go left as far as possible" loop above), as it's a common follow-up.

## Common Pitfalls

1. **Missing the null check** at the start of a recursive function.
2. **Confusing height and depth** (edges vs nodes; check what the problem counts).
3. **BFS without fixing the level size:** use `for _ in range(len(q))` so you process exactly one level per iteration.
4. **Returning the wrong thing** in "global answer + return value" problems (return the one-sided path, store the two-sided one).
5. **Using `queue.shift()` in JS** inside BFS on big trees: O(n) per shift (swap queues per level instead).

## Quick Reference

```text
DFS: if not node: return base; left = f(node.left); right = f(node.right); return combine(node, left, right)
BFS: q = [root]; while q: for _ in range(len(q)): node = q.popleft(); push children
Pre = state down · Post = summaries up · In = sorted order in a BST
O(n) time · O(h) stack for DFS · O(width) queue for BFS
```