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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Rolling Hashes and Substring Fingerprints.
Least You Need to Know: Rolling Hashes and Substring FingerprintsRelated lessons
Keep going with nearby lessons in the same topic.