Dividing Problems for Recursive Solutions

Divide the problem means find a self-similar substructure: left/right subtrees, prefix/suffix, or independent components—then glue results.

Why this shows up in the real world

Puzzle games, constraint solvers, and interview combinatorial search all share the same skeleton: build state, recurse, undo.

Core idea (explained for students)

Identify independent subproblems for parallelism; if overlapping, switch to memoization or DP instead of naive recursion.

Try this in Python

def tree_sum(root: dict | None) -> int:
    if root is None:
        return 0
    return root['val'] + tree_sum(root.get('left')) + tree_sum(root.get('right'))


t = {'val': 2, 'left': {'val': 1, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}
print(tree_sum(t))

Common mistakes

• Split that shares mutable state—race or wrong answer.
• Base case on wrong granularity (split mid-element wrong for BST property).

Key takeaways

• Draw input instance with indices annotated.
• Template: def solve(lo, hi): inclusive ranges.