# Tree Traversals — Part 2: Interview Problems

Six problems: bottom-up summaries (depth, diameter, max path sum), structural changes, BFS by level, and the classic LCA search.

## 1. Maximum Depth of Binary Tree (LeetCode 104)

**🟢 Easy.** Return the number of nodes along the longest root-to-leaf path.

```text
[3,9,20,null,null,15,7] → 3
```

**Approach.** Bottom-up: depth(node) = 1 + max(depth(left), depth(right)); an empty tree has depth 0.

**Complexity.** O(n) time, O(h) stack.

```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 {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
```

```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

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

## 2. Invert Binary Tree (LeetCode 226)

**🟢 Easy.** Mirror a binary tree (swap every node's left and right children) and return its root.

```text
[4,2,7,1,3,6,9] → [4,7,2,9,6,3,1]
```

**Approach.** Swap the children of the current node and recurse into both (any traversal order works).

**Complexity.** O(n) time, O(h) stack.

```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 invertTree(root: TreeNode | null): TreeNode | null {
  if (root) [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return 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

def invert_tree(root):
    if root:
        root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root
```

## 3. Binary Tree Level Order Traversal (LeetCode 102)

**🟠 Medium.** Return the node values level by level, left to right.

```text
[3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]
```

**Approach.** BFS with a queue. Each outer iteration processes exactly the nodes currently in the queue (one level), collecting their values and enqueueing their children.

**Complexity.** O(n) time, O(width) space.

```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 levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  let level: TreeNode[] = [root];
  while (level.length) {
    res.push(level.map((n) => n.val));
    const next: TreeNode[] = [];
    for (const n of level) {
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    level = next;
  }
  return res;
}
```

```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 level_order(root):
    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
```

## 4. Diameter of Binary Tree (LeetCode 543)

**🟢 Easy.** Return the length (in edges) of the longest path between any two nodes.

```text
[1,2,3,4,5] → 3   (path 4-2-1-3 or 5-2-1-3)
```

**Approach.** Postorder: each call returns its height; at each node, the longest path *through* it is `leftHeight + rightHeight`, which updates a global maximum. The path doesn't have to pass through the root.

**Complexity.** O(n) time, O(h) stack.

```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 diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;
  const height = (node: TreeNode | null): number => {
    if (!node) return 0;
    const lh = height(node.left), rh = height(node.right);
    best = Math.max(best, lh + rh);
    return 1 + Math.max(lh, rh);
  };
  height(root);
  return best;
}
```

```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

def diameter_of_binary_tree(root):
    best = 0

    def height(node):
        nonlocal best
        if not node:
            return 0
        lh, rh = height(node.left), height(node.right)
        best = max(best, lh + rh)            # path through this node
        return 1 + max(lh, rh)               # height reported to the parent

    height(root)
    return best
```

## 5. Lowest Common Ancestor of a Binary Tree (LeetCode 236)

**🟠 Medium.** Given two nodes `p` and `q` in a binary tree, return their lowest common ancestor (a node can be its own ancestor).

```text
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 → 3
```

**Approach.** Postorder search: return the node if it is p or q; otherwise recurse left and right. If both sides return something, the current node is the LCA; if only one side does, pass that result up.

**Complexity.** O(n) time, O(h) stack.

```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 lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}
```

```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

def lowest_common_ancestor(root, p, q):
    if not root or root is p or root is 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                      # p and q are on different sides
    return left or right
```

## 6. Binary Tree Maximum Path Sum (LeetCode 124)

**🔴 Hard.** A path is any sequence of connected nodes (each used once, not necessarily through the root). Return the maximum path sum. Values may be negative.

```text
[-10,9,20,null,null,15,7] → 42   (15 → 20 → 7)
```

**Approach.** Postorder. `gain(node)` returns the best sum of a path that starts at node and goes **down one side**: `node.val + max(0, gain(left), gain(right))` (negative branches are dropped with `max(0, …)`). At each node, the best path **through** it is `node.val + max(0, gainL) + max(0, gainR)`, which updates the global answer.

**Complexity.** O(n) time, O(h) stack.

```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 maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const gain = (node: TreeNode | null): number => {
    if (!node) return 0;
    const left = Math.max(0, gain(node.left)), right = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
  };
  gain(root);
  return best;
}
```

```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

def max_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(0, gain(node.left))
        right = max(0, gain(node.right))
        best = max(best, node.val + left + right)   # path bending at this node
        return node.val + max(left, right)          # one side only, for the parent

    gain(root)
    return best
```