Algorithms / Recursion Tree Pruning

Least You Need to Know: Recursion Trees, Feasibility Checks, and Pruning

A recursion tree shows the search branches a backtracking algorithm may explore. **Pruning** means cutting off branches as soon as a partial state can no longer lead to a valid or useful solution.

The least you need to know

The recursion tree branches according to the remaining choices at each step.
Pruning is correct only when you can justify that no completion of the current partial state can succeed.
Earlier feasibility checks save work because they prevent exploring full subtrees of impossible states.
Pruning changes the amount of search performed, not the definition of a valid solution.
Worst-case backtracking can still be exponential even when practical pruning helps a lot.

Key notation

branch one recursive choice from the current partial state

prune stop exploring a branch that cannot help

feasibility check test whether the current partial state can still lead to a solution

Tiny worked example

Imagine placing queens row by row.
If a partial placement already has two queens attacking each other, no extension of that placement can become valid.
So you stop there instead of exploring the rest of that subtree.
That saved work is the whole point of pruning.

Common mistakes

Students often confuse pruning with memoization; pruning discards impossible branches, while memoization reuses repeated subproblems.
Students often think any heuristic preference is pruning even when it does not actually eliminate branches.
Students often assume pruning guarantees polynomial time, which it does not.

How to recognize this kind of problem

You can reject a partial candidate before it is complete.
The problem has constraints like no conflicts, no repeated use, or bounds that can already fail early.
A recursion tree picture helps explain why an early check removes an entire subtree.