9. Trees

Key Insight

95% of tree problems are solved with DFS (recursive post-order for bottom-up info, pre-order for top-down). Internalize: what info do I need from my children to answer the question at each node?

9.1 Node Definition

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

---

9.2 Traversals

# --- Recursive traversals ---
def inorder(root: TreeNode | None) -> list[int]:
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

def preorder(root: TreeNode | None) -> list[int]:
    return [root.val] + preorder(root.left) + preorder(root.right) if root else []

def postorder(root: TreeNode | None) -> list[int]:
    return postorder(root.left) + postorder(root.right) + [root.val] if root else []

# --- Iterative inorder (avoids recursion limit) ---
def inorder_iter(root: TreeNode | None) -> list[int]:
    stack, res = [], []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur); cur = cur.left
        cur = stack.pop()
        res.append(cur.val)
        cur = cur.right
    return res

# --- Level order (BFS) ---
from collections import deque
def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    q = deque([root])
    res = []
    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

---

9.3 Core Tree Algorithms

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

# --- Diameter of binary tree ---
def diameter(root: TreeNode | None) -> int:
    res = [0]
    def dfs(node: TreeNode | None) -> int:
        if not node:
            return 0
        l, r = dfs(node.left), dfs(node.right)
        res[0] = max(res[0], l + r)
        return 1 + max(l, r)
    dfs(root)
    return res[0]

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

# --- Lowest Common Ancestor (LCA) — BST ---
def lca_bst(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    cur = root
    while cur:
        if p.val < cur.val and q.val < cur.val:
            cur = cur.left
        elif p.val > cur.val and q.val > cur.val:
            cur = cur.right
        else:
            return cur
    return cur  # never None if p, q in tree

# --- LCA — general binary tree ---
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

# --- Validate BST ---
def is_valid_bst(root: TreeNode | None) -> bool:
    def validate(node, lo, hi):
        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"))

# --- Serialize / Deserialize binary tree ---
def serialize(root: TreeNode | None) -> str:
    res = []
    def dfs(node):
        if not node:
            res.append("N"); return
        res.append(str(node.val))
        dfs(node.left); dfs(node.right)
    dfs(root)
    return ",".join(res)

def deserialize(data: str) -> TreeNode | None:
    vals = iter(data.split(","))
    def dfs():
        v = next(vals)
        if v == "N":
            return None
        node = TreeNode(int(v))
        node.left = dfs(); node.right = dfs()
        return node
    return dfs()

# --- Construct tree from preorder + inorder ---
def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    mid = inorder.index(preorder[0])
    root.left  = build_tree(preorder[1:mid+1], inorder[:mid])
    root.right = build_tree(preorder[mid+1:],  inorder[mid+1:])
    return root
    # O(n²) — for O(n): pre-build {val: index} map for inorder

---

9.4 Key CP Patterns

Problem	DFS return value	Global tracked
Height	int depth	—
Diameter	int depth	max l+r
Max path sum	int max one-side gain	max node + l + r
Count nodes	int count	—
Is balanced	int height or -1	—
Any root-to-leaf path sum	bool	—

---