The Decision Tree Grows

Backtracking code is short, but the execution it unleashes is a whole tree of possibilities. This animation makes that tree physical: every recursive call sprouts a node showing the partial solution at that moment, growing downward as the recursion deepens.

Three things happen to a branch. If the partial solution completes validly, it flashes green and flies to the results shelf. If it breaks a rule, it flashes red and the branch withers and retracts — that retraction is the undo step running, handing the shared state back untouched. Otherwise it keeps sprouting children, one per remaining choice.

What to watch for:

• The breadcrumb bar at the top is the single shared path object. Watch it push a choice on the way down and pop it on the way back up — perfectly nested, like matched parentheses.
• Pruned branches die early, high up the tree. Every node that never gets drawn is work saved; that is why pruning checks belong at the branch point, not at the leaves.
• Only one path from the root is ever lit at a time. The tree looks huge, but the algorithm only ever holds one root-to-node path in memory — that is why space stays O(n) while time is exponential.