Math for coding interviews/Decision trees - branching choices
Decision Trees and Backtracking, Explained Visually
Backtracking builds a tree of decisions. At each step you have some number of choices (say, k choices). Each choice leads to another set of k choices, and so on. The total number of paths through this tree is k^depth. For k=2 and depth=n, that is 2ⁿ paths.
See it for yourself
A tree where each node has multiple branches. At depth 0: 1 node. At depth 1: k nodes. At depth 2: k² nodes. At depth 3: k³ nodes. The tree widens rapidly.
Decision trees - branching choices
Backtracking builds a tree of decisions. At each step you have some number of choices (say, k choices). Each choice leads to another set of k choices, and so on. The total number of paths through this tree is k^depth. For k=2 and depth=n, that is 2ⁿ paths.
Think of it this way: A menu with 3 courses and 5 choices per course. Total possible meals = 5×5×5 = 125. The decision tree has 3 levels and branches 5 ways at each level.
For algorithms: Backtracking explores this decision tree but prunes branches early when a partial solution is already invalid. Good pruning turns an unworkable O(k^n) into something practical.
Real-world analogy
A menu with 3 courses and 5 choices per course. Total possible meals = 5×5×5 = 125. The decision tree has 3 levels and branches 5 ways at each level.
Why it matters in interviews
Backtracking explores this decision tree but prunes branches early when a partial solution is already invalid. Good pruning turns an unworkable O(k^n) into something practical.