7. Trees

What Interviewers Test Here

• DFS (recursive) for structural questions (height, paths, diameter)
• BFS (iterative) for level-based questions (level order, minimum depth)
• Knowing when to propagate info upward (post-order) vs downward (pre-order)
• BST properties for $O(\log n)$ solutions

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

from collections import deque

# --- Height ---
def height(root: TreeNode | None) -> int:
    if not root: return 0
    return 1 + max(height(root.left), height(root.right))

# --- Level order (BFS) ---
def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root: return []
    result, 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)
        result.append(level)
    return result

# --- Lowest Common Ancestor ---
def lca(root: TreeNode | None, p: TreeNode, q: TreeNode) -> TreeNode | None:
    if not root or root is p or root is q:
        return root
    left  = lca(root.left,  p, q)
    right = lca(root.right, p, q)
    return root if left and right else (left or right)

# --- Maximum path sum ---
def max_path_sum(root: TreeNode | None) -> int:
    best = [float("-inf")]
    def dfs(node: TreeNode | None) -> int:
        if not node: return 0
        l = max(dfs(node.left),  0)   # discard negative gain
        r = max(dfs(node.right), 0)
        best[0] = max(best[0], node.val + l + r)
        return node.val + max(l, r)
    dfs(root)
    return best[0]

---

Conceptual Q&A

Q1: "When would you use DFS vs BFS on a tree?"

Walkthrough:

"DFS explores a full path to a leaf before backtracking. Use it when:

• You need information from children to compute a parent's answer (post-order: height, diameter, path sum)
• You're searching any path or need the structure of subtrees
• You're checking a property that must hold for all nodes

BFS explores level by level. Use it when:

• You want the shortest path or minimum depth (guaranteed since BFS finds level-minimal solutions)
• The problem mentions 'level', 'row', 'depth', 'nearest'
• You need to process nodes in the order of their distance from the root

Rule of thumb: if the problem mentions levels or minimum distance → BFS. Everything else → DFS."

---

Q2: "Find the diameter of a binary tree (longest path between any two nodes)."

Walkthrough:

"The diameter is the longest path between any two nodes. A path may or may not pass through the root.

For each node, the longest path through it = left_height + right_height. I want the maximum of this over all nodes.

This screams post-order DFS: process children first, then compute the answer at the current node. I'll have the DFS return the height of the subtree (for parent use), while tracking the global maximum diameter.

$O(n)$ time — visits each node once."

def diameter(root: TreeNode | None) -> int:
    max_diam = [0]
    def dfs(node: TreeNode | None) -> int:
        if not node: return 0
        left  = dfs(node.left)
        right = dfs(node.right)
        max_diam[0] = max(max_diam[0], left + right)  # path through node
        return 1 + max(left, right)                   # height returned upward
    dfs(root)
    return max_diam[0]

# Example tree:
#       1
#      / \
#     2   3
#    / \
#   4   5
# dfs(4)=1, dfs(5)=1, at node 2: diam=2, height=2
# at node 3: diam=0, height=1
# at node 1: diam=max(2, 2+1=3) = 3

---

Q3: "Validate that a binary tree is a valid BST."

Walkthrough:

"A BST requires: all nodes in the left subtree < root, all in right subtree > root. Crucially, this must hold for the entire subtree, not just immediate children.

Common mistake: only check node.left.val < node.val. This fails for:

    5
   / \
  1   4
     / \
    3   6

4 < 5 locally, but 4 should be in the right subtree (>5) — invalid BST.

Correct approach: pass min and max bounds down during DFS. Each node must satisfy lo < node.val < hi. Root starts with $(-\infty, +\infty)$. $O(n)$ time."

def is_valid_bst(root: TreeNode | None) -> bool:
    def validate(node, lo: float, hi: float) -> bool:
        if not node: return True
        if not (lo < node.val < hi): return False
        return (validate(node.left,  lo,       node.val) and
                validate(node.right, node.val, hi))
    return validate(root, float("-inf"), float("inf"))

---