# How the Preorder Traversal Template Works for Backtracking Problems in Hello-Algo

> Explore the preorder traversal template in Hello-Algo for backtracking. Learn how it combines DFS and state management to efficiently solve problems.

- Repository: [Yudong Jin/hello-algo](https://github.com/krahets/hello-algo)
- Tags: deep-dive
- Published: 2026-02-25

---

**The preorder traversal template in Hello-Algo combines depth-first search with explicit state management to systematically explore solution spaces, using helper functions to separate problem-specific logic from the generic backtracking engine.**

The Hello-Algo repository provides a comprehensive implementation of the preorder traversal template for backtracking problems, demonstrating how to evolve from simple tree traversal to a reusable algorithmic framework. This pattern appears in the backtracking chapter where three progressive examples illustrate state management, choice pruning, and solution recording. Understanding this template helps developers apply systematic depth-first exploration to combinatorial search problems.

## Understanding the Preorder Traversal Backtracking Pattern

The preorder traversal template treats the search space as a decision tree where each node represents a state and each edge represents a choice. Unlike simple traversal that only visits nodes, backtracking requires maintaining and restoring state as the algorithm explores different branches. The Hello-Algo implementation follows a consistent six-step pattern: checking for solutions, recording valid states, iterating over available choices, pruning invalid paths, making choices to update state, and undoing choices to backtrack.

## Three Implementation Examples in Hello-Algo

The repository provides three progressive implementations in `codes/go/chapter_backtracking/`, each building upon the previous pattern to demonstrate increasing abstraction.

### Example I: Basic Preorder Traversal (preOrderI)

The first example implements a simple depth-first search without explicit backtracking state management. Located in [`preorder_traversal_i_compact.go`](https://github.com/krahets/hello-algo/blob/main/preorder_traversal_i_compact.go), this function collects all nodes with value 7 using natural recursion unwinding.

```go
func preOrderI(root *TreeNode, res *[]*TreeNode) {
    if root == nil { return }
    if root.Val.(int) == 7 {          // solution test
        *res = append(*res, root)    // record the solution
    }
    preOrderI(root.Left,  res)       // explore left subtree
    preOrderI(root.Right, res)       // explore right subtree
}

```

This version requires no manual state restoration because the recursion stack itself manages the traversal path. The `TreeNode` type definition resides in [`pkg/tree_node.go`](https://github.com/krahets/hello-algo/blob/main/pkg/tree_node.go).

### Example II: Path Recording with Backtracking (preOrderII)

The second example in [`preorder_traversal_ii_compact.go`](https://github.com/krahets/hello-algo/blob/main/preorder_traversal_ii_compact.go) demonstrates explicit state management by tracking the current root-to-node path. This pattern requires manual backtracking to maintain path integrity across sibling subtrees.

```go
func preOrderII(root *TreeNode, res *[][]*TreeNode, path *[]*TreeNode) {
    if root == nil { return }

    *path = append(*path, root)           // try a choice (push)
    if root.Val.(int) == 7 {              // solution check
        *res = append(*res, append([]*TreeNode{}, *path...))
    }

    preOrderII(root.Left,  res, path)    // recurse left
    preOrderII(root.Right, res, path)    // recurse right

    *path = (*path)[:len(*path)-1]       // undo choice (pop)
}

```

The `path` slice acts as mutable state that grows when entering a node and shrinks when leaving, ensuring that each recursive call operates on the correct partial path. This explicit push-pop pattern forms the foundation of backtracking algorithms.

### Example III: Generic Backtracking Template (backtrackIII)

The third example in [`preorder_traversal_iii_template.go`](https://github.com/krahets/hello-algo/blob/main/preorder_traversal_iii_template.go) abstracts the backtracking mechanics into a reusable framework. This template separates problem-specific logic from the generic traversal engine through helper functions.

The implementation defines five key operations:

- **Solution test** – `isSolution` checks if the current state satisfies the goal (value equals 7)
- **Recording** – `recordSolution` copies the current state into the result set
- **Validity pruning** – `isValid` discards illegal choices (nil nodes or nodes with value 3)
- **State transition** – `makeChoice` pushes a node onto the state
- **Backtracking** – `undoChoice` pops the node from the state

```go
func backtrackIII(state *[]*TreeNode, choices *[]*TreeNode, res *[][]*TreeNode) {
    if isSolution(state) {               // 1️⃣ check solution
        recordSolution(state, res)       // 2️⃣ record it
    }
    for _, choice := range *choices {    // 3️⃣ iterate over choices
        if isValid(state, choice) {      // 4️⃣ prune invalid choices
            makeChoice(state, choice)    // 5️⃣ try (push)
            // next level choices are the children of the current node
            next := [] *TreeNode{choice.Left, choice.Right}
            backtrackIII(state, &next, res)
            undoChoice(state, choice)    // 6️⃣ backtrack (pop)
        }
    }
}

```

A concrete compact implementation (`preOrderIII`) in [`preorder_traversal_iii_compact.go`](https://github.com/krahets/hello-algo/blob/main/preorder_traversal_iii_compact.go) demonstrates the same pruning logic without the helper abstraction, offering a middle ground between template verbosity and raw recursion.

## How the Template Handles State and Choices

The preorder traversal template treats the binary tree as an implicit state graph where each node represents a decision point. The algorithm maintains two key data structures: the `state` slice tracking the current path from root to the current node, and the `choices` slice containing candidate nodes for the next step.

When the algorithm visits a node, it executes a six-phase cycle:

1. **Check** – Determine if the current state constitutes a valid solution using `isSolution`
2. **Record** – Save a copy of the state to the results if it is a solution
3. **Iterate** – Loop through available choices (typically left and right children)
4. **Validate** – Skip choices that violate constraints using `isValid`
5. **Choose** – Update the state by appending the current choice (`makeChoice`)
6. **Backtrack** – Remove the choice from state after exploring all descendants (`undoChoice`)

This explicit state management distinguishes backtracking from simple traversal. While `preOrderI` relies on the implicit call stack, `preOrderII` and the generic template manually control the `path` or `state` slice to ensure that sibling subtrees do not interfere with each other's state.

## Summary

- The **Hello-Algo** repository implements three progressive versions of preorder traversal for backtracking, located in `codes/go/chapter_backtracking/`
- **Example I** ([`preorder_traversal_i_compact.go`](https://github.com/krahets/hello-algo/blob/main/preorder_traversal_i_compact.go)) demonstrates simple DFS without explicit state management, suitable for problems requiring only node visitation
- **Example II** ([`preorder_traversal_ii_compact.go`](https://github.com/krahets/hello-algo/blob/main/preorder_traversal_ii_compact.go)) introduces manual path tracking with push-pop backtracking, essential for problems requiring root-to-node path information
- **Example III** ([`preorder_traversal_iii_template.go`](https://github.com/krahets/hello-algo/blob/main/preorder_traversal_iii_template.go)) abstracts the pattern into a reusable template with helper functions (`isSolution`, `isValid`, `makeChoice`, `undoChoice`) separating problem logic from traversal mechanics
- All examples rely on the `TreeNode` type defined in [`pkg/tree_node.go`](https://github.com/krahets/hello-algo/blob/main/pkg/tree_node.go) and demonstrate how preorder traversal serves as the foundation for systematic backtracking search

## Frequently Asked Questions

### What is the difference between basic preorder traversal and the backtracking template?

Basic preorder traversal (`preOrderI`) only visits nodes and records values without maintaining explicit state between recursive calls. The backtracking template (`backtrackIII`) explicitly manages state through `makeChoice` and `undoChoice` operations, allowing the algorithm to track paths, prune invalid branches, and restore state when exploring sibling subtrees.

### How does the state restoration work in the Hello-Algo backtracking template?

State restoration occurs through the `undoChoice` function, which typically pops the last element from the state slice (`*path = (*path)[:len(*path)-1]`). This operation executes after the recursive call returns, ensuring that when the algorithm backtracks to explore a different branch, the state reflects only the path to the current node, not including previously explored descendants.

### Can the preorder traversal template be used for non-tree problems?

Yes, the template generalizes to any problem that can be modeled as a state-space search with choices and constraints. While the Hello-Algo examples use binary trees (where choices are left and right children), the `backtrackIII` template works for combinatorial problems like subsets, permutations, and N-Queens by redefining `choices` as candidate elements and adjusting the `isValid` and `isSolution` logic accordingly.

### Where are the helper functions defined in the Hello-Algo repository?

The helper functions for the generic template (`isSolution`, `isValid`, `makeChoice`, `undoChoice`, `recordSolution`) are defined in [`codes/go/chapter_backtracking/preorder_traversal_iii_template.go`](https://github.com/krahets/hello-algo/blob/main/codes/go/chapter_backtracking/preorder_traversal_iii_template.go). The `TreeNode` struct and utility functions like `SliceToTree` reside in [`codes/go/pkg/tree_node.go`](https://github.com/krahets/hello-algo/blob/main/codes/go/pkg/tree_node.go). Concrete implementations that inline these operations appear in [`preorder_traversal_iii_compact.go`](https://github.com/krahets/hello-algo/blob/main/preorder_traversal_iii_compact.go) for comparison.