Search as Tree Traversal

Every Brute-Force Search Is a Tree

Here's an observation that changes how you think about search problems: every brute-force search defines an implicit tree of decisions.

You don't build this tree in memory. You don't allocate nodes. But the structure is there, hiding in the recursion. Each recursive call is a node. Each choice you make — "put a queen in column 0," "try column 1 instead" — is a branch.

Understanding this tree is the key to understanding why some searches are fast and why others take the age of the universe.

N-Queens: The Decision Tree

Problem: Place \(n\) queens on an \(n \times n\) chessboard so that no two queens threaten each other. Queens attack along rows, columns, and diagonals.

For \(n = 4\), you have a \(4 \times 4\) board. You place queens one row at a time. In row 0, you have 4 column choices. In row 1, you have 4 column choices. And so on.

The full decision tree (without any pruning) looks like this:

                        root
              /      |       |      \
          col=0    col=1   col=2   col=3     ← row 0
         /||\     /||\     /||\    /||\
        0123     0123     0123    0123       ← row 1
       (each has 4 children)                 ← row 2
       (each has 4 children)                 ← row 3

This tree has \(4^4 = 256\) leaves. Every leaf represents a complete placement of 4 queens — most of which are invalid (queens attacking each other). Brute force would check all 256 leaves.

Full decision tree for 4-Queens without pruning has 256 leaves

Pruning: Cutting Branches

But you don't need to explore the full tree. If you place a queen in row 0, column 0, and then try row 1, column 0 — stop. Two queens are in the same column. No matter what you do in rows 2 and 3, this placement is invalid.

That's pruning. You cut the entire subtree below the invalid node.

Let's trace the actual exploration for \(n = 4\). We place queens row by row and prune invalid branches.

Row 0: Try column 0

Q . . .
. . . .
. . . .
. . . .

Row 1: Try each column

Column 0: same column as row 0. Pruned.
Column 1: diagonal with row 0. Pruned.
Column 2: safe. Place queen.

Q . . .
. . Q .
. . . .
. . . .

Row 2 (with Q at (0,0) and (1,2)):

Column 0: same column as row 0. Pruned.
Column 1: diagonal with row 1. Pruned.
Column 2: same column as row 1. Pruned.
Column 3: diagonal with row 1. Pruned.

All columns pruned. Backtrack to row 1, try column 3.

Q . . .
. . . Q
. . . .
. . . .

Row 2 (with Q at (0,0) and (1,3)):

Column 0: same column as row 0. Pruned.
Column 1: safe. Place queen.

Q . . .
. . . Q
. Q . .
. . . .

Row 3 (with Q at (0,0), (1,3), (2,1)):

Column 0: same column as row 0. Pruned.
Column 1: same column as row 2. Pruned.
Column 2: diagonal with row 2. Pruned.
Column 3: same column as row 1. Pruned.

All pruned. Backtrack. Eventually, the algorithm finds two solutions:

Solution 1:          Solution 2:
. Q . .              . . Q .
. . . Q              Q . . .
Q . . .              . . . Q
. . Q .              . Q . .

The Exploration Summary

Metric	Full tree	With pruning
Total nodes	\(1 + 4 + 16 + 64 + 256 = 341\)	17 nodes explored
Leaf nodes checked	256	2 valid solutions found
Branches pruned	0	24 column attempts rejected

Pruning eliminated over 95% of the tree.

The Tree You Don't Draw

The speedup from pruning comes from the subtrees you never enter. Every pruned branch represents an exponential number of leaf nodes you didn't check.

When you prune at row 1 (depth 1 in the tree), you skip \(4^2 = 16\) descendants. When you prune at row 0, you'd skip \(4^3 = 64\) descendants. The earlier you prune, the more work you avoid.

This is why the isSafe check happens before recursing, not after. You want to detect conflicts as early as possible — at the shallowest depth in the tree.

The Code

bool isSafe(vector<int>& queens, int row, int col) {
    for (int previousRow = 0; previousRow < row; previousRow++) {
        if (queens[previousRow] == col) return false;
        if (abs(queens[previousRow] - col) == abs(previousRow - row)) return false;
    }
    return true;
}

void solveNQueens(vector<int>& queens, int row, int boardSize,
                  vector<vector<int>>& allSolutions) {
    if (row == boardSize) {
        allSolutions.push_back(queens);
        return;
    }
    for (int col = 0; col < boardSize; col++) {
        if (isSafe(queens, row, col)) {
            queens[row] = col;
            solveNQueens(queens, row + 1, boardSize, allSolutions);
        }
    }
}

queens[i] = j means there's a queen in row \(i\), column \(j\). The isSafe function checks column conflicts and diagonal conflicts against all previously placed queens.

The recursion IS the tree traversal. Each for loop over columns is the branching. The isSafe check is the pruning. Reaching row == boardSize is reaching a valid leaf.

We show you the mental model here. The DP course will cover backtracking techniques in depth — constraint propagation, symmetry breaking, iterative deepening, and other methods for making the search tree even smaller.

Decision tree for 4-Queens

Pruned decision tree for 4-Queens: invalid branches are cut early

The General Principle

Any problem where you make a sequence of choices can be modeled as a tree: - Subsets: include or exclude each element → binary tree of depth \(n\), \(2^n\) leaves - Permutations: choose the next element → tree of depth \(n\) with \(n!\) leaves - N-Queens: choose a column per row → tree of depth \(n\) with \(n^n\) leaves (unpruned)

The brute-force complexity is the number of leaves. Pruning reduces the tree. The art of backtracking is designing constraints that prune as aggressively and as early as possible.

Try It

The starter code counts nodes explored and branches pruned for \(n = 4\).

Predict before running: The full tree has \(1 + 4 + 16 + 64 + 256 = 341\) nodes. How many does pruning eliminate?

Challenge: Run the code for \(n = 8\). The full tree would have \(8^8 \approx 16.7\) million leaves. How many nodes does the pruned search actually explore? (It's around 15,000 — a 1000x reduction.)

Challenge 2: What happens if you move the isSafe check inside the recursive call (check after placing the queen) instead of before? The answer is the same, but more nodes are visited. Why? Count the difference.

Edge Cases to Watch For

\(n = 2\) and \(n = 3\) (no valid solutions): Every placement leads to conflicts. The pruned tree explores a few nodes and backtracks completely. Returning 0 solutions is a valid output — your code must handle "no solution found" gracefully.
Checking safety after vs before recursion: If you place the queen first and then check, you still get the correct answer but visit more nodes. The pruning is less effective because you enter subtrees before detecting the conflict.
Symmetric solutions: For \(n = 4\), the two solutions are mirror images. Exploiting symmetry can cut the search space in half, but the basic backtracking doesn't do this — if symmetry reduction is applied incorrectly, you'll undercount.

Problems

Problem	Link	Difficulty
LC 51 — N-Queens	leetcode.com/problems/n-queens	Hard
LC 52 — N-Queens II	leetcode.com/problems/n-queens-ii	Hard
LC 37 — Sudoku Solver	leetcode.com/problems/sudoku-solver	Hard