Discrete Mathsfor Engineers

4. Search Tree & Recursion Structure

Backtracking algorithms explore a conceptual structure: the search tree.

At the same time, they are implemented using recursion. Understanding how these two views align is essential.

4.1 The Search Tree

The search space of a backtracking problem can be visualized as a tree.

• The root represents the empty solution
• Each level corresponds to one decision
• Each edge represents a choice
• Each node represents a partial solution

A node at depth i corresponds to a sequence (x₁, …, xᵢ).

4.2 Depth and Decision Levels

The depth of a node in the tree corresponds directly to the number of decisions made.

If a problem has n variables, the tree has at most n levels.

4.3 Recursion as Tree Traversal

Each recursive call corresponds to one node in the search tree.

• Entering a recursive call = moving down the tree
• Returning from a call = moving back up

Therefore, the algorithm performs a depth-first traversal of the search tree.

4.4 The Call Stack

The recursion stack stores the path from the root to the current node.

At any moment, the stack contains:

• the current partial solution
• the active sequence of decisions

Stack depth = tree depth.

4.5 Why Backtracking Uses DFS

Backtracking naturally follows a depth-first strategy because it explores one branch fully before trying another.

This is efficient because:

• it uses limited memory (only one path at a time)
• it allows early pruning of invalid branches

4.6 Visual Intuition

You can think of backtracking as:

1. Going down a path (making choices)
2. Reaching a dead end or solution
3. Going back up (undo)
4. Trying a different branch

4.7 Why This Matters

Understanding this structure is critical because:

• it explains how recursion works internally
• it clarifies how pruning reduces complexity
• it helps reason about performance

Without this mental model, backtracking often feels like “magic recursion”.