Trees

🧠 Spot It

• Problem involves hierarchical data, parent-child relationships
• Asks for path, depth, lowest common ancestor, validation
• DFS → path/property problems | BFS → level-by-level problems

---

Pattern 1 — DFS (Recursive)

def dfs(node):
    if not node:
        return  # base case
    # Pre-order: process node first
    dfs(node.left)
    # In-order: process node between children (BST sorted order)
    dfs(node.right)
    # Post-order: process node after children

---

Pattern 2 — BFS (Level Order)

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):  # process entire level
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

---

Pattern 3 — Path Problems

# Max path sum through any node
def max_path_sum(root):
    res = [root.val]
    def dfs(node):
        if not node: return 0
        left = max(dfs(node.left), 0)   # ignore negative paths
        right = max(dfs(node.right), 0)
        res[0] = max(res[0], node.val + left + right)  # update global
        return node.val + max(left, right)  # return single branch
    dfs(root)
    return res[0]

---

BST Properties

• Left subtree values < node < right subtree values
• In-order traversal gives sorted sequence
• Search / Insert / Delete → O(log N) avg, O(N) worst (unbalanced)

---

Problems

---

Notes

<!-- Add your own observations as you solve problems -->