Tree traversal without using the built-in stack in C++

26 January 2026

I have written these code snippets too often, so I might as well share them. The reason for not using recursion – and thus relying on the built-in stack – is that for large values for N, the stack trace will become hard to debug and read, and you might create a stack overflow if the stack size is set too conservatively.

The functions are templated, but they don’t have to be.

Given the following tree:

1
2
3
4
5
6
          o
         / \
        /   \
       o     o
      / \   / \
     o   o o   o

Depth-first search (DFS) #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
template <typename F>
void dfs(const Node& from, F&& f) {
    std::stack<std::reference_wrapper<const Node>> stack;
    stack.emplace(from);

    while (!stack.empty()) {
        const Node& current = stack.top();
        stack.pop();

        // execute callback
        f(current);

        // add child nodes to the stack
        for (const Node& child : current.children()) {
            stack.emplace(child);
        }
    }
}

This results in the nodes being called in the following order:

1
2
3
4
5
6
          0
         / \
        /   \
       1     4
      / \   / \
     2   3 5   6

Note that if you want to ensure that the left-most children in Node::children() are called before right-most children, you have to iterate over the children in reverse.

Breadth-first search (BFS) #

This is exactly the same algorithm as DFS, but then with a queue instead of a stack. The result is that we first visit all nodes at the first depth, then the second depth, etc.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
template <typename F>
void bfs(const Node& from, F&& f) {
    std::queue<std::reference_wrapper<const Node>> queue;
    queue.emplace(from);

    while (!queue.empty()) {
        const Node& current = queue.front();
        queue.pop();

        // execute callback
        f(current);

        // add child nodes to the stack
        for (const Node& child : current.children()) {
            queue.emplace(child);
        }
    }
}

This results in the nodes being called in the following order:

1
2
3
4
5
6
          0
         / \
        /   \
       1     2
      / \   / \
     3   4 5   6

Post-order traversal #

This is a variant of DFS, where we visit child nodes before parent nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <typename F>
void dfs_postorder(const Node& from, F&& f) {
    struct StackFrame{
        const Node& node;
        bool visited;
    };
    std::stack<StackFrame> stack;
    stack.emplace(from, false);

    while (!stack.empty()) {
        StackFrame current = stack.top();
        stack.pop();

        if (current.visited) {
            // execute callback
            f(current.node);
            continue;
        }

        // not visited, so add to stack again, but now visited
        stack.emplace(current.node, true);

        // add child nodes to the stack
        for (const Node& child : current.node.children()) {
            stack.emplace(child, false);
        }
    }
}

This results in the nodes being called in the following order:

1
2
3
4
5
6
          6
         / \
        /   \
       2     5
      / \   / \
     0   1 3   4