Trees — Master Recap & Pattern Cheatsheet

def dfs(node):
    if not node: return
    # preorder: process here
    dfs(node.left)
    # inorder: process here
    dfs(node.right)
    # postorder: process here

from collections import deque
def bfs(root):
    q = deque([root])
    while q:
        for _ in range(len(q)):
            node = q.popleft()
            # process
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)

def dp(node):
    if not node: return base_case
    left = dp(node.left)
    right = dp(node.right)
    # combine and return
    global_max = max(global_max, combine(left, right))
    return value_for_parent(left, right, node)

def validate(node, mn=float('-inf'), mx=float('inf')):
    if not node: return True
    if not (mn < node.val < mx): return False
    return validate(node.left, mn, node.val) and            validate(node.right, node.val, mx)

def lca(root, p, q):
    if not root or root == p or root == 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

# Path sum with prefix sums
def pathSum(root, targetSum):
    prefix = {0: 1}
    def dfs(node, cur):
        if not node: return 0
        cur += node.val
        count = prefix.get(cur - targetSum, 0)
        prefix[cur] = prefix.get(cur, 0) + 1
        count += dfs(node.left, cur) + dfs(node.right, cur)
        prefix[cur] -= 1
        return count
    return dfs(root, 0)

def serialize(root):
    def dfs(node):
        if not node: return ['#']
        return [str(node.val)] + dfs(node.left) + dfs(node.right)
    return ','.join(dfs(root))

def deserialize(data):
    vals = iter(data.split(','))
    def build():
        val = next(vals)
        if val == '#': return None
        node = TreeNode(int(val))
        node.left, node.right = build(), build()
        return node
    return build()

LOG = 16
up = [[-1]*LOG for _ in range(n)]
for i in range(n): up[i][0] = parent[i]
for j in range(1, LOG):
    for i in range(n):
        if up[i][j-1] != -1:
            up[i][j] = up[up[i][j-1]][j-1]

# DFS1: compute from one root
# DFS2: recompute all others in O(n) using formula
# dist[child] = dist[parent] - cnt[child] + (n - cnt[child])