The Recursion Tree

Start with the initial call as the root. Label each node with the state that matters, not every local variable. For subsets, use the current index and path. For permutations, use the prefix and remaining unused values. For a board, use the row or cell being filled plus the placements already made.

Then draw children by applying each legal next choice. Stop at base cases and explicitly mark whether the leaf records an answer, returns false, or gets pruned. A small input is enough; the goal is insight, not a complete picture for large n.

Leaves often correspond to complete candidates. Subset recursion with include or exclude has 2^n leaves because every element has two outcomes. Permutation recursion has n! leaves because the first position has n choices, the second has n - 1, and so on.

Counting leaves gives a lower bound on time when the problem must output all solutions. If there are 2^n subsets, no algorithm can list them in less than O(2^n) output steps.

Time is not only leaves. Every internal node also does work: checking constraints, looping over choices, marking state, and undoing state. For many backtracking families, the number of internal nodes is within the same exponential order as the leaves, so the leaf count gives the right growth class.

When branching factor varies, use an upper bound. If every level has at most b choices and depth at most d, the tree has at most 1 + b + b^2 + ... + b^d nodes, which is O(b^d) for b > 1.

A pruned branch is a node whose children are never drawn. Marking those cuts on the recursion tree helps interviewers see exactly what your optimization saves. It also protects correctness because you can explain why the omitted subtree cannot contain a useful answer.

For duplicate pruning, the tree shows that two sibling edges would produce the same set of descendants. For bound pruning, it shows that a partial state lacks enough remaining choices or has already exceeded a target.