Decision Tree Thinking in Backtracking
Why Draw the Tree First?
A backtracking function is just a walk over a tree that you never actually build. Each function call is a node. Each loop iteration that leads into a recursive call is an edge. If you can sketch that tree on paper for a tiny input, the code almost writes itself.
TREE PART MEANS IN CODE ────────── ───────────────────────────────────────── Root The first call, with an empty partial answer Level (depth d) The d-th decision being made Edge One option chosen at that decision Node A partial answer (the path from the root) Leaf A call that returns without recursing further Pruned edge An option rejected by the validity check Depth of tree Maximum recursion depth → stack space Number of nodes Roughly the running time
The Three Questions
Before writing code, answer these three questions out loud.
1. WHAT IS DECIDED AT EACH LEVEL? "Whether element i is in the group" → take/skip shape "Which element comes next in the group" → pick-next shape "What goes in position i" → slot-filling shape 2. WHAT ARE THE BRANCHES AT A NODE? take / skip → 2 branches any element after the last → (n - start) branches any unused element → (n - depth) branches 3. WHEN IS A NODE AN ANSWER? Only at leaves (depth = n)? → record in the base case At every node? → record at the top of the function
Shape 1: Take / Skip (Binary Tree)
Each level looks at one element and makes a yes/no decision about it. The tree is perfectly binary and every leaf sits at depth n.
Elements: a, b, c
Level 0: decide a Level 1: decide b Level 2: decide c
{}
take a / \ skip a
{a} {}
take b / \ skip take b/ \ skip
{a,b} {a} {b} {}
/ \ / \ / \ / \
{a,b,c} {a,b} {a,c} {a} {b,c} {b} {c} {}
Leaves (depth 3) = the 8 subsets
Internal nodes = 7 (not answers — still undecided)
Total nodes = 15 = 2^(n+1) - 1
This shape is easiest when each element has a small, fixed set of fates (in / out, or "colour 1 / colour 2 / colour 3").
Shape 2: Pick-Next (N-ary Tree with a Start Index)
Each level asks "which element do I add next?" — but only elements after the last one picked are allowed. This prevents the same group appearing twice in a different order.
Elements: a, b, c (start index shown as s)
{} s=0
/ | \
{a}s=1 {b}s=2 {c}s=3
/ \ |
{a,b}s=2 {a,c} {b,c}
|
{a,b,c}
Every node is a subset → record at every node
Total nodes = 8 = 2^n (no wasted internal nodes)
Same 8 answers, roughly half the nodes. This is also the shape used for combinations ("choose k of n") — you simply stop once the group has k elements.
Shape 3: Slot-Filling (N-ary Tree with a Used Set)
Each level fills one position of the answer with any element not yet used. This produces orderings, not groups.
Elements: a, b, c
[]
/ | \
[a] [b] [c]
/ \ / \ / \
[a,b] [a,c] [b,a] [b,c] [c,a] [c,b]
| | | | | |
[a,b,c][a,c,b][b,a,c][b,c,a][c,a,b][c,b,a]
Branches shrink by 1 per level: 3 → 2 → 1
Leaves = 3! = 6 orderings
Watching the Trees in Code
The program below prints each call as an indented line, so you can see the tree the recursion walks. The take/skip version prints 15 nodes; the pick-next version prints 8.
import java.util.ArrayList;
import java.util.List;
public class DecisionTrees {
static String[] items = {"a", "b", "c"};
static int nodes;
static String fmt(List<String> path) {
return "{" + String.join(",", path) + "}";
}
// Shape 1 — one level per element, two branches: take / skip
static void takeSkip(int i, List<String> path, int depth) {
nodes++;
boolean leaf = (i == items.length);
System.out.println(" ".repeat(depth) + fmt(path) + (leaf ? " <- answer" : ""));
if (leaf) return;
path.add(items[i]); // take items[i]
takeSkip(i + 1, path, depth + 1);
path.remove(path.size() - 1); // undo
takeSkip(i + 1, path, depth + 1); // skip items[i]
}
// Shape 2 — every node is an answer, branches = elements after start
static void pickNext(int start, List<String> path, int depth) {
nodes++;
System.out.println(" ".repeat(depth) + fmt(path));
for (int j = start; j < items.length; j++) {
path.add(items[j]);
pickNext(j + 1, path, depth + 1);
path.remove(path.size() - 1);
}
}
public static void main(String[] args) {
System.out.println("Take / skip tree:");
nodes = 0;
takeSkip(0, new ArrayList<>(), 0);
System.out.println("nodes visited = " + nodes);
System.out.println();
System.out.println("Pick-next tree:");
nodes = 0;
pickNext(0, new ArrayList<>(), 0);
System.out.println("nodes visited = " + nodes);
}
}Output:
Take / skip tree:
{}
{a}
{a,b}
{a,b,c} <- answer
{a,b} <- answer
{a}
{a,c} <- answer
{a} <- answer
{}
{b}
{b,c} <- answer
{b} <- answer
{}
{c} <- answer
{} <- answer
nodes visited = 15
Pick-next tree:
{}
{a}
{a,b}
{a,b,c}
{a,c}
{b}
{b,c}
{c}
nodes visited = 8
Read the indentation as depth. In the first tree, a node like {a} appears three times at different depths — it is the same partial answer, but with different decisions still pending. In the second tree, every line is a finished subset.
Choosing the Right Shape
ASK USE
───────────────────────────────────────────── ──────────────────
Does order inside an answer matter?
No (groups, subsets, combinations) Take/skip or pick-next
Yes (orderings, arrangements, sequences) Slot-filling + used set
Is every position filled from a fixed menu?
e.g. phone digits → letters, light on/off Slot-filling, menu per level
Do you need "exactly k" or "sum to target"?
Pick-next — stop when k reached or sum hit Pick-next with a stop rule
Does each element have more than two fates?
e.g. put item i into bucket 0, 1, or 2 Take/skip generalised:
one level per item,
one branch per bucket
From Tree to Code: A Mechanical Mapping
Once the tree is sketched, translate it line by line.
TREE SKETCH CODE ─────────────────────────── ───────────────────────────────────── "Each level decides element i" function parameter: i (or start) "Leaves are answers" if i == n: record copy; return "Every node is an answer" record copy as the FIRST line "Branches: take / skip" two recursive calls, undo between them "Branches: elements after s" for j in s..n-1: recurse with j+1 "Branches: unused elements" for j in 0..n-1: if not used[j]: ... "This branch breaks a rule" if invalid: continue (pruned edge) "Depth = n" recursion depth n → O(n) stack space
Practice: Sketch Before You Code
Try sketching these trees for a tiny input before reading the dedicated pages.
1. Every way to choose 2 of {p, q, r, s}
→ pick-next, stop at size 2. Expect 6 leaves.
2. Every 3-character code where position 1 ∈ {x, y},
position 2 ∈ {1, 2, 3}, position 3 ∈ {!, ?}
→ slot-filling with a different menu per level. Expect 2·3·2 = 12 leaves.
3. Split {4, 5, 6} into two groups (group A and group B)
→ take/skip generalised: each element → A or B. Expect 2^3 = 8 leaves.
4. Every ordering of {1, 2, 3, 4} where 1 is not in the first position
→ slot-filling, prune "1 at depth 0". Expect 4! - 3! = 18 leaves.
Common Mistakes
Mixing two shapes in one function. A loop over "all elements after start" plus a separate skip call generates every subset multiple times. Pick one shape and stick to it.
Recording answers at the wrong place. In the take/skip shape, internal nodes are unfinished — recording them adds duplicates. In the pick-next shape, recording only at depth n loses every smaller subset.
Using a start index where order matters. Pick-next with a start index can never produce [b, a]. For orderings, use a used set and loop from 0.
Forgetting that the tree you draw is the time you pay. If your sketch for n = 4 already has hundreds of nodes, the real input will be too slow — look for pruning or a DP reformulation.
Interview Questions
Q: How do you decide what a level of the recursion represents?
Look at what the answer is made of. If an answer is "a set of chosen elements", a level can be "the fate of element i" (take/skip) or "the next chosen element" (pick-next). If an answer is "a sequence with positions", a level is "what goes in position i". Choose the one where the validity rules are easiest to check on a partial answer.
Q: Why does the pick-next tree for subsets have exactly 2ⁿ nodes?
Every node corresponds to one distinct increasing sequence of indices, and every subset has exactly one such sequence. So there is a one-to-one match between nodes and subsets, giving 2ⁿ nodes including the empty root.
Q: How does drawing the tree help with complexity analysis?
The number of nodes bounds the number of calls, the depth bounds the stack space, and the number of leaves times the cost of copying an answer bounds the output cost. Reading these three numbers off a sketch gives the full time and space complexity.
Summary
- ›A backtracking function walks a tree of decisions — sketch it before you code.
- ›Answer three questions: what is decided per level, what are the branches, when is a node an answer.
- ›Three common shapes: take/skip (binary), pick-next (start index, groups), slot-filling (used set, orderings).
- ›The sketch tells you the base case, the loop, the pruning point, and the complexity.
Next, Time & Space Complexity turns these tree sketches into concrete bounds such as O(2ⁿ · n) and O(n! · n).
In a backtracking decision tree, what does one LEVEL usually represent?