Introduction

A depth-first iterator is a clean way to walk a tree without exposing traversal details to the rest of your code. In Python, the simplest implementation uses an explicit stack, which keeps the traversal iterative, easy to test, and safe from recursion-depth limits on deep trees.

Define a Tree Structure That Is Easy to Traverse

The iterator only needs one thing from each node: access to its children. A small dataclass is enough for many examples and keeps the traversal code focused on the algorithm instead of container boilerplate.

1from dataclasses import dataclass, field
2
3@dataclass
4class Node:
5    value: str
6    children: list["Node"] = field(default_factory=list)

This structure works for a general tree, not only a binary tree. That makes the iterator more reusable for menus, file-like hierarchies, abstract syntax trees, and dependency graphs that have already been reduced to tree form.

Implement Preorder DFS With an Explicit Stack

A depth-first preorder iterator visits a node first and then explores its descendants. The stack holds the work that remains, and reversing the child list preserves left-to-right order during traversal.

1class DepthFirstIterator:
2    def __init__(self, root: Node):
3        self._stack = [root]
4
5    def __iter__(self) -> "DepthFirstIterator":
6        return self
7
8    def __next__(self) -> Node:
9        if not self._stack:
10            raise StopIteration
11
12        node = self._stack.pop()
13        self._stack.extend(reversed(node.children))
14        return node

The reversed call matters. Because a stack is last in, first out, pushing children in reverse order causes the leftmost child to be visited first when the next iteration happens.

Use the Iterator on a Real Tree

Once the iterator exists, client code becomes straightforward. The caller can loop over nodes without knowing anything about stack management.

1root = Node(
2    "A",
3    children=[
4        Node("B", children=[Node("D"), Node("E")]),
5        Node("C", children=[Node("F")]),
6    ],
7)
8
9for node in DepthFirstIterator(root):
10    print(node.value)

The output is:

1A
2B
3D
4E
5C
6F

That ordering is preorder DFS: parent first, then each subtree in order.

Consider a Generator for a Lighter Interface

If you do not need a dedicated iterator class, a generator can express the same traversal more compactly. The tradeoff is that the traversal logic is no longer packaged as an object with its own state.

1def depth_first(root: Node):
2    stack = [root]
3    while stack:
4        node = stack.pop()
5        yield node
6        stack.extend(reversed(node.children))
7
8values = [node.value for node in depth_first(root)]
9print(values)

For many applications, the generator version is enough. A separate iterator class is more useful when you want to attach options such as filtering, maximum depth, or alternative traversal orders.

Extend the Pattern Carefully

The same skeleton can support postorder traversal, depth limits, or node filtering, but those features change how state is stored. For example, postorder often requires either a visited marker or a stack of tuples that track whether a node's children have already been processed.

The important design rule is to keep the iterator's contract simple. Decide whether it yields nodes, values, or paths, and keep that choice consistent. That makes the rest of your code easier to reason about because callers know exactly what one iteration step returns.

Common Pitfalls

• Forgetting to reverse the child list before pushing onto the stack, which silently reverses the traversal order.
• Using recursive DFS for very deep trees and then hitting Python's recursion limit.
• Mutating the tree while iterating, which can cause skipped nodes or repeated nodes depending on when the children list changes.
• Applying the iterator to a graph with cycles, which can loop forever unless you track visited nodes.
• Mixing node objects and node values in the same iterator API, which makes callers guess what each iteration step returns.

Summary

• A depth-first iterator is easiest to implement with an explicit stack.
• Reversing the child order preserves natural left-to-right traversal.
• Yield nodes when you want flexibility, or values when you want a narrower API.
• A generator is often enough, but an iterator class is easier to extend.
• Treat graphs with cycles as a different problem from ordinary tree traversal.