A Tutorial on Depth-First Search for Tree and Graph Traversal

Depth-first search (DFS) is a fundamental algorithm for visiting the vertices of a tree or graph. It follows one path as far as possible before backtracking, making it useful for tasks such as searching, path detection, tree ordering, connected-component analysis, and cycle detection.

The method is simple enough to implement in a few lines, yet its behaviour depends heavily on the data structure and the way visited nodes are tracked. This tutorial explains the core idea, recursive and iterative implementations, complexity, common mistakes, and practical examples in Python.

Understanding The Depth-First Strategy

Imagine exploring a network of walking tracks. At each junction, you choose an unvisited track and continue until there are no unexplored options. You then return to the last junction with another available route. DFS follows this same pattern: choose a neighbour, visit it, and recursively or iteratively explore its neighbours before returning.

For a tree, there is exactly one path between the root and any other node, so a visited set is often unnecessary. A graph can contain cycles and multiple routes to the same vertex, so every graph traversal should generally record visited vertices. Without that record, a cycle such as A -> B -> C -> A can cause an infinite loop.

The order in which neighbours are stored affects the traversal sequence, but not the basic algorithm. For example, if a graph stores neighbours alphabetically, DFS will produce a predictable order. If neighbours come from a set or an unordered source, the result may vary between executions.

Representing Trees And Graphs

A binary tree can be represented with a node containing a value and references to a left and right child:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

A general graph is commonly stored as an adjacency list. In Python, a dictionary maps each vertex to a list of directly connected vertices:

graph = {
    "Sydney": ["Melbourne", "Brisbane"],
    "Melbourne": ["Perth"],
    "Brisbane": ["Sydney"],
    "Perth": []
}

This representation uses space proportional to the number of vertices and edges. It is usually preferable for sparse networks, such as transport connections or web links. An adjacency matrix uses a two-dimensional array and offers constant-time edge lookup, but it requires O(V²) memory, which can be wasteful when most possible connections do not exist.

When graph data is loaded from files or services, preprocessing can be a significant part of the task. A comparison of tabular and columnar processing appears in a data pipeline review, and the same principle applies here: clean, consistent identifiers make traversal much easier to reason about.

Recursive Tree Traversal

The recursive version of DFS mirrors its definition closely. A function processes the current node, then explores each child. For a binary tree, the position of the visit determines the traversal type:

• Pre-order: visit the node, then the left and right subtrees.
• In-order: visit the left subtree, then the node, then the right subtree.
• Post-order: visit both subtrees, then the node.

Here is a pre-order traversal:

def preorder(node):
    if node is None:
        return

    print(node.value)
    preorder(node.left)
    preorder(node.right)

In-order traversal is especially useful for a binary search tree because it produces values in sorted order:

def inorder(node, result):
    if node is None:
        return

    inorder(node.left, result)
    result.append(node.value)
    inorder(node.right, result)

The recursion depth is equal to the tree height. A balanced tree has height near log₂(n), while a highly unbalanced tree can have height n. Python may raise a RecursionError for a very deep tree, so iterative DFS is safer when input height is uncontrolled.

Using A Stack Instead Of Recursion

An explicit stack provides the same last-in, first-out behaviour as the program’s call stack. To perform pre-order traversal, push the root, remove one node at a time, and then push its children. Since the right child is pushed first, the left child is processed first.

def iterative_preorder(root):
    if root is None:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.value)

        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)

    return result

The order of those two append operations is important. A stack removes the most recently added item, so reversing the push order changes the traversal sequence. This detail is easy to overlook when converting recursive code to an iterative form.

The same pattern works for a general graph, with a visited set added before expanding neighbours. An explicit stack is often suitable for production code that may receive deep input, particularly when a service processes large user-generated structures.

Traversing Graphs Safely

A graph DFS should mark a vertex as visited when it is discovered. Marking it too late can place the same vertex on the stack several times, increasing work and potentially creating incorrect behaviour in cyclic graphs.

def dfs(graph, start):
    visited = set()
    order = []
    stack = [start]

    while stack:
        vertex = stack.pop()

        if vertex in visited:
            continue

        visited.add(vertex)
        order.append(vertex)

        for neighbour in reversed(graph.get(vertex, [])):
            if neighbour not in visited:
                stack.append(neighbour)

    return order

The reversed call is optional. It simply preserves the natural left-to-right order when the stack is used. The get method also makes the function tolerant of a starting vertex that has no entry in the adjacency list.

Starting from one vertex visits only the reachable component. To traverse every component, loop through all vertices and begin a new DFS whenever a vertex has not yet been visited:

def all_components(graph):
    visited = set()
    components = []

    for vertex in graph:
        if vertex in visited:
            continue

        component = []
        stack = [vertex]
        visited.add(vertex)

        while stack:
            current = stack.pop()
            component.append(current)

            for neighbour in graph.get(current, []):
                if neighbour not in visited:
                    visited.add(neighbour)
                    stack.append(neighbour)

        components.append(component)

    return components

This approach is useful for grouping disconnected records, such as separate clusters of roads or independent relationships in a dataset. In Australia, a network model might include routes within Sydney and Melbourne as separate components if no cross-city links are represented.

Complexity And Implementation Choices

With an adjacency list, DFS visits each reachable vertex once and examines each relevant edge once, giving time complexity O(V + E). The visited set, stack, and output require O(V) additional space. For a tree with n nodes, there are n - 1 edges, so the time complexity simplifies to O(n).

With an adjacency matrix, checking a neighbour row requires scanning up to V entries for each visited vertex. The resulting time complexity is commonly O(V²), although the matrix can be valuable when the graph is dense or constant-time edge lookup matters more than memory usage.

Memory limits also influence the representation. A Python set is convenient but has significant object overhead. For vertices identified by consecutive integers, a list of Boolean values or a bytearray can reduce memory consumption. In C, arrays and manually managed stacks can provide tighter control, while a circular buffer is a useful related structure for fixed-capacity streaming workloads; see this C buffer implementation for the underlying storage idea.

DFS is often preferred over breadth-first search when the goal involves fully exploring branches, detecting cycles, or producing finishing times. BFS is usually a better choice for the shortest path in an unweighted graph because it examines vertices by distance from the source.

Detecting Paths, Cycles, And Ordering

DFS can answer whether a path exists between two vertices. Stop when the target is discovered, or store a parent mapping so that the complete path can be reconstructed:

def find_path(graph, start, target):
    stack = [start]
    parent = {start: None}

    while stack:
        current = stack.pop()

        if current == target:
            path = []
            while current is not None:
                path.append(current)
                current = parent[current]
            return path[::-1]

        for neighbour in graph.get(current, []):
            if neighbour not in parent:
                parent[neighbour] = current
                stack.append(neighbour)

    return None

For an undirected graph, an edge leading to an already visited vertex is a cycle only when that vertex is not the current node’s parent. For a directed graph, cycle detection commonly uses three states: unvisited, currently exploring, and completely explored. Finding an edge to a currently exploring vertex reveals a back edge and therefore a cycle.

The same three-state technique supports topological sorting of a directed acyclic graph. DFS explores dependencies first, then places each vertex into a result list after its outgoing edges have been processed. Reversing that list gives an ordering in which prerequisites appear before dependent tasks. A heap can provide another ordering strategy when repeatedly selecting the smallest available item; a Python example is discussed in binary heap implementation.

Testing Traversals In Real Programs

Good tests should include an empty tree, a single node, a balanced tree, and a severely skewed tree. For graphs, include an isolated vertex, duplicate edges, a cycle, disconnected components, and a missing or invalid starting vertex. These cases expose assumptions that a simple connected example will not reveal.

Traversal output should be tested separately from traversal side effects. A function that returns a list is easier to verify than one that prints directly, while a parent map is better when callers need to reconstruct paths. Deterministic neighbour ordering also makes unit tests stable.

Real applications may need to handle private or sensitive information. For example, a graph built from customer relationships or location records should be designed with the Australian Privacy Act 1988 and the Australian Privacy Principles in mind. Data minimisation, controlled access, and removal of unnecessary identifiers matter before an algorithm begins, especially when a prototype could later be used in a commercial Australian market.

DFS remains a compact building block for larger systems. It powers directory searches, dependency analysis, compiler passes, puzzle solving, connected-component labelling, and many coding interview problems. Once the stack, visited-state rules, and complexity analysis are clear, the same pattern can be adapted to trees, directed graphs, undirected networks, and more specialised data structures.