8.2 Depth-First Search Traversal

Depth-first search (DFS) is the fundamental traversal technique for trees.

algorithmstreesdata-structures

8.2 Depth-First Search Traversal

Depth-first search (DFS) is the fundamental traversal technique for trees. Nearly every tree algorithm builds upon it. Subtree sizes, heights, diameters, lowest common ancestors, dynamic programming on trees, Heavy-Light Decomposition, Centroid Decomposition, and many other techniques begin with some variation of DFS.

The central idea is simple: visit a node, recursively process its children, then return to the parent. Despite its simplicity, DFS exposes the hierarchical structure of a tree in a way that makes many otherwise difficult problems straightforward.

This recipe introduces DFS traversal patterns and shows how to use them as building blocks for larger algorithms.

Problem

You need to visit every node in a tree exactly once while preserving parent-child relationships.

Solution

For a rooted tree represented as child lists, a recursive DFS is straightforward:

package main

import "fmt"

func dfs(tree [][]int, node int) {
    fmt.Println(node)

    for _, child := range tree[node] {
        dfs(tree, child)
    }
}

Given the tree:

0
├── 1
│   ├── 3
│   └── 4
└── 2
    ├── 5
    └── 6

the traversal produces:

0
1
3
4
2
5
6

Each node is visited before its descendants.

For an undirected tree, pass the parent node so the traversal does not revisit the edge it just came from:

func dfs(adj [][]int, node, parent int) {
    fmt.Println(node)

    for _, next := range adj[node] {
        if next == parent {
            continue
        }

        dfs(adj, next, node)
    }
}

This pattern appears throughout the remainder of this chapter.

Discussion

A depth-first traversal naturally creates a call stack that mirrors the path from the root to the current node.

Consider this tree:

0
├── 1
│   └── 3
└── 2

The traversal begins at node 0.

Visit 0

It then descends into node 1.

Visit 1

Then into node 3.

Visit 3

Since node 3 has no children, the traversal returns to node 1, then to node 0, and finally explores node 2.

The sequence of recursive calls creates an implicit stack:

0
└── 1
    └── 3

When recursion returns, nodes are removed from the stack in reverse order.

Many tree algorithms exploit this behavior. Information can flow downward from ancestors to descendants during recursion and upward from descendants to ancestors during return.

Preorder Traversal

The previous examples visit nodes before processing children.

This ordering is called preorder traversal.

func preorder(tree [][]int, node int) {
    fmt.Println(node)

    for _, child := range tree[node] {
        preorder(tree, child)
    }
}

For the sample tree:

0
├── 1
│   ├── 3
│   └── 4
└── 2

the output is:

0 1 3 4 2

Preorder traversal is useful when a node must be processed before its descendants.

Examples include:

  • Serialization
  • Path construction
  • Tree copying
  • Hierarchical rendering

Postorder Traversal

Sometimes a node depends on information computed by its children.

In that case, process the children first.

func postorder(tree [][]int, node int) {
    for _, child := range tree[node] {
        postorder(tree, child)
    }

    fmt.Println(node)
}

The output becomes:

3 4 1 2 0

Postorder traversal is one of the most important patterns in tree algorithms.

Subtree size computation is a classic example:

func subtreeSize(tree [][]int, node int, size []int) {
    size[node] = 1

    for _, child := range tree[node] {
        subtreeSize(tree, child, size)
        size[node] += size[child]
    }
}

Each node waits until all descendants have been processed before calculating its own result.

Computing Depth

DFS can carry information from parent to child.

The depth of a node is the number of edges from the root.

func computeDepth(
    tree [][]int,
    node int,
    currentDepth int,
    depth []int,
) {
    depth[node] = currentDepth

    for _, child := range tree[node] {
        computeDepth(
            tree,
            child,
            currentDepth+1,
            depth,
        )
    }
}

For the sample tree:

depth[0] = 0
depth[1] = 1
depth[2] = 1
depth[3] = 2
depth[4] = 2

The traversal propagates information downward as it explores the tree.

Computing Heights

Height flows in the opposite direction.

A node's height depends on the heights of its children.

func height(tree [][]int, node int) int {
    maxHeight := 0

    for _, child := range tree[node] {
        h := height(tree, child)

        if h > maxHeight {
            maxHeight = h
        }
    }

    return maxHeight + 1
}

Leaves return height 1.

Internal nodes combine the results from their children.

This is another example of postorder computation.

Iterative DFS

Recursion is elegant, but an explicit stack sometimes provides better control.

func iterativeDFS(adj [][]int, root int) {
    stack := []int{root}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        fmt.Println(node)

        for i := len(adj[node]) - 1; i >= 0; i-- {
            stack = append(stack, adj[node][i])
        }
    }
}

The explicit stack performs the same role as the recursive call stack.

Iterative implementations are useful when:

  • Trees are extremely deep.
  • Stack overflow is a concern.
  • Traversal order requires precise control.
  • Recursive overhead becomes significant.

Complexity Analysis

Let:

  • n be the number of nodes.
  • n - 1 be the number of edges.

Every node is visited exactly once.

Every edge is examined a constant number of times.

Therefore:

Operation Complexity
DFS traversal O(n)
Memory (recursive) O(h)
Memory (iterative) O(h)

where h is the height of the tree.

For a balanced tree:

h = O(log n)

For a degenerate chain:

h = O(n)

The worst-case memory consumption depends on tree shape rather than node count alone.

Common Mistakes

One common mistake is forgetting the parent check in an undirected tree:

for _, next := range adj[node] {
    dfs(adj, next, node)
}

This immediately creates infinite recursion because traversal repeatedly walks back and forth along the same edge.

Another mistake is performing expensive work repeatedly inside recursive calls.

Consider:

for _, child := range tree[node] {
    subtreeSize(tree, child, size)
}

for _, child := range tree[node] {
    size[node] += size[child]
}

This works, but performs two passes over the children. Combining the operations into a single loop reduces overhead and simplifies reasoning.

A third mistake is assuming recursion depth is small. Trees generated from linked-list-like structures can have depth proportional to the number of nodes.

Takeaway

Depth-first search is the primary mechanism for exploring trees. The traversal exposes the recursive structure of the data and naturally supports information flowing downward from ancestors or upward from descendants. Preorder traversal processes nodes before children, postorder traversal processes children before parents, and both patterns appear repeatedly in advanced tree algorithms. Once DFS becomes second nature, many seemingly complex tree problems reduce to deciding what information should travel along the traversal.