Depth-First Search Algorithm: Trees, Graphs, and Six Interview Patterns

Go Deep Before Going Wide

You're exploring a building you've never been in. Walk through the front door, take the first hallway left, keep turning left at every junction, go until you hit a dead end, then backtrack and try a different direction. You don't start a new wing until you've fully exhausted the current one.

That instinct is depth-first search.

DFS is a traversal algorithm that follows each path to its end before considering alternatives. Sounds almost embarrassingly simple. But that single idea is the foundation for connected components, cycle detection, topological ordering, path finding, and most binary tree problems you'll see in an interview. One idea. Six patterns. An unreasonable number of LeetCode problems.

Start With a Tree

Trees are the cleanest place to see DFS. No cycles. No drama. Just nodes and children.

A DFS starting at 1 visits: 1 → 2 → 4 → 5 → 3.

It goes left as far as possible (1 → 2 → 4), hits a leaf, backtracks to 2, visits 5, then backtracks all the way to 1 and finally visits 3. At no point does it sneak over to 3 while the left subtree is still waiting. DFS is patient. Methodical. The opposite of how you feel in an interview.

Here's the recursive implementation:

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

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

    print(node.val)   # visit the node
    dfs(node.left)    # go deep left
    dfs(node.right)   # go deep right

That's it. The recursion is the stack. Each time dfs(node.left) is called, the current frame pauses and the algorithm burrows deeper. Elegant when it works, mildly horrifying to explain at 9am.

Pre-, In-, Postorder: Same Algorithm, Different Timing

The code above visits the current node before its children. That's preorder (root → left → right). Move the print line and you get completely different orderings with identical traversal logic:

def preorder(node):    # root → left → right
    if not node:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

def inorder(node):     # left → root → right
    if not node:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

def postorder(node):   # left → right → root
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

Inorder traversal on a BST produces values in sorted ascending order. That property shows up constantly in tree problems. Postorder is the right choice when a parent's answer depends on its children's answers first, like computing subtree heights or checking subtree validity.

Same algorithm. One line moves. Three entirely different behaviors. The interview question "which traversal would you use?" has exactly one correct answer, and you derive it by asking what the parent needs to know before processing itself.

Graphs Need a Visited Set. Trees Don't.

Trees have no cycles. Graphs do. Run the recursive DFS above on a graph with a cycle and watch your terminal spin indefinitely. Python will be polite enough to crash after 1,000 frames. C++ will just eat your stack and shrug.

The fix is a visited set:

def dfs_graph(graph, node, visited=None):
    if visited is None:
        visited = set()

    visited.add(node)
    print(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_graph(graph, neighbor, visited)

The visited set is the only structural difference between tree DFS and graph DFS. On a tree, there are no cycles by definition, so you skip it. On a graph, it's mandatory. Forget it in an interview and you'll spend three minutes explaining why your program is "still running."

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}

dfs_graph(graph, 0)
# visits: 0, 1, 3, 2

Starting at 0, the algorithm visits 0, dives into neighbor 1, dives into neighbor 3 (0 is already visited), hits a dead end, backtracks twice to 0, then visits 2.

When Recursion Runs Out of Stack

Python's default call stack limit is 1,000 frames. Exactly 1,000. Not 1,001. On a large graph or a deeply skewed tree, you'll hit a RecursionError so fast it feels personal. The fix is an explicit stack on the heap:

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

    while stack:
        node = stack.pop()
        if node in visited:
            continue

        visited.add(node)
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

The behavior is still depth-first. You've just moved the implicit call stack into an explicit data structure. Visit order may differ slightly from the recursive version (neighbors are pushed in adjacency-list order and popped in reverse) but the traversal is depth-first either way.

When an interviewer says "now can you do it iteratively?", this is all they want. The while loop is not harder to write than the recursive version once you've seen it. It just looks different enough to shake you if you haven't practiced it.

Depth-First Search Time and Space Complexity

DFS visits every vertex and every edge exactly once, giving O(V + E) time. For a tree with n nodes (exactly n - 1 edges), that simplifies to O(n).

Space is more subtle. The recursion stack holds one frame per level of depth. On a balanced binary tree, depth is O(log n). On a path graph where each node has one child, depth is O(n). The space cost is the maximum recursion depth, not the total number of nodes. Graph DFS also needs the visited set, which is O(V).

Scenario	Time	Space
Tree DFS	O(n)	O(h) where h is tree height
Graph DFS	O(V + E)	O(V) visited set + O(depth) stack
Balanced binary tree	O(n)	O(log n)
Path graph or fully skewed tree	O(n)	O(n)

If you're using an adjacency matrix instead of an adjacency list, time becomes O(V²) because checking all neighbors takes O(V) per node regardless of actual edge count. Mentioning this unprompted in an interview signals that you understand the representation trade-off, not just the algorithm.

Six Interview Patterns That Are Really Just DFS

DFS isn't one pattern. It's the foundation for several, and interviewers know it.

Path problems. Does a path exist between two nodes? What are all paths from root to leaf? DFS naturally tracks the current path through the recursion stack, making it cleaner than BFS for problems that need the actual path, not just whether one exists.

Connected components. Run DFS from every unvisited node. Each separate top-level call discovers one component. This is the core of Number of Islands, Friend Circles, and similar region-counting problems. The structure is always the same: outer loop over all nodes, DFS on each unvisited one, increment a counter.

Cycle detection. Track which nodes are currently on the recursion stack. If you reach a node already in the current path, you've found a cycle. In directed graphs, the three-color approach (unvisited / in-progress / done) handles this cleanly.

Topological sort. Run DFS on a directed acyclic graph and push each node onto a result stack after all its descendants have been processed (postorder). Reverse the stack. That's a valid topological ordering. Course scheduling and build dependency problems use this pattern.

Tree problems. Maximum depth, diameter, lowest common ancestor, path sum variants, tree serialization. The traversal order determines what's easy to compute at each node.

Backtracking. DFS with an undo step. The algorithm explores a choice, recurses, then un-makes that choice before trying the next one. The call stack carries the current partial state. Combinations, permutations, subsets, N-Queens all use this pattern.

The distinction between plain DFS and backtracking trips people up in interviews. DFS marks nodes visited and doesn't revisit them. Backtracking undoes choices and may revisit the same node through different paths. The DFS vs Backtracking breakdown covers where the line is and why it matters for problem recognition.

What the Problem Is Telling You

When you see these phrases, DFS is almost certainly the right tool:

"all paths from root to leaf"
"number of connected regions / islands / components"
"detect a cycle"
"valid ordering of prerequisites"
"find if a path exists"
"maximum depth / height"

The giveaway is that you need to explore deeply into a structure before knowing whether a branch is valid. BFS gives you the same connectivity answer, but DFS is the natural fit when state accumulates along a path (current sum, current path, current choices) because that state lives in the call stack automatically.

When the problem asks for shortest path or minimum steps, that's BFS territory. BFS vs DFS walks through the decision quickly. For a pattern-first breakdown of which problems map to DFS, DFS pattern recognition organizes problems by structural signal, not problem name.

Writing DFS Under Pressure

Reading DFS is easy. Writing it under pressure, while talking out loud, while someone stares at your screen waiting for you to remember what a base case is, is a different sport entirely.

The failure modes are predictable: forgetting the base case, omitting the visited set on a graph problem, freezing on the iterative version, explaining preorder when the problem actually needs postorder.

The gap between understanding DFS conceptually and executing it fluently in a live interview is larger than most engineers expect. If you want to close that gap, SpaceComplexity runs voice-based mock interviews where an AI interviewer asks graph and tree problems in real time and gives rubric-based feedback on your communication and your approach, not just whether the code compiles.