DFS — depth-first search

1 · Why DFS matters: the intuition

Depth-first search is the algorithmic encoding of "explore one branch fully before backing up to try the next". On a graph with V nodes and E edges, it visits every node and traverses every edge in O(V + E) time and O(V) space (the recursion stack plus the visited set). That's optimal for "exhaustive but unordered" exploration — the moment you don't care about path lengths, DFS is the cheapest tool that touches everything at least once.

The recursive/stack-based duality is the conceptual core. Recursive DFS uses the call stack to remember "what to do after this subtree". Iterative DFS makes that stack explicit — usually a slice or array of "work items". The two are operationally equivalent; you choose recursive for clarity (the code reads top-down like the problem) or iterative for control (when the input might blow the language's default recursion limit, which in Python is 1,000 and in many other languages is in the tens of thousands).

DFS is also the right shape when the problem says "any" rather than "shortest". "Find any path from A to B": DFS returns the first one it finds. "Find all configurations": DFS with backtracking enumerates them. "Is the graph acyclic": DFS detects a back-edge in one pass. None of these have an ordering constraint that would require BFS's layer-by-layer discipline.

2 · How to recognise it: six distinct shapes

• "Does a path exist" / "is X reachable from Y". The classic reachability question. DFS gives a yes/no with no extra work.
• Connected components. Loop over all nodes; DFS from each unvisited one; increment a counter. The cleanest connected-components pattern.
• Cycle detection. Especially in directed graphs. Three-colour DFS detects back-edges directly.
• Tree traversals. Pre/in/post-order. Each is a one-line variation on the same recursive shape.
• "All paths" or "all configurations". When you need to enumerate (not just check), DFS with backtracking is usually cleaner than BFS.
• Implicit graph traversal. Grid problems where you want to fill / flood. DFS via recursion is often shorter than BFS via a queue.

Shape A: connected components

"How many separate islands / regions / components are there?" Outer loop iterates every node; whenever you find one that's unvisited, DFS-flood from it and increment a counter. The set of nodes discovered during one DFS call is one component. Examples: LC 200 Number of Islands, LC 547 Number of Provinces, LC 695 Max Area of Island.

Shape B: cycle detection (different mechanics for directed vs undirected)

Undirected: a back-edge to anyone other than the parent is a cycle. Pass parent down the recursion; ignore the edge back to the parent. Two-colour visited set is sufficient.
Directed: a two-colour scheme can't tell back-edges from cross-edges. Use three-colour: WHITE (unseen) → GREY (on the current recursion stack) → BLACK (fully explored). A GREY hit is a cycle. The classic example is course-schedule cycle detection (LC 207).

Shape C: path between two nodes (or all paths)

"Does any path exist from A to B?": DFS from A, return true on finding B. "Find any one path": same DFS, accumulate the path on the stack frame, return when found. "Find all paths": DFS with backtracking; on success, copy the path into the result; on the way back, pop the last node. Examples: LC 797 All Paths From Source to Target, LC 1971 Find if Path Exists in Graph.

Shape D: island / region counting on a grid

A grid is an implicit graph: every cell is a node; neighbours are the four (or eight) adjacent cells. Loop over the grid; for each unvisited land cell, DFS-flood and mark visited. The number of DFS calls that found new land = the number of islands. Mutating the grid in-place ('1' → '0') is a clean way to mark visited without an extra set. LC 200 is the canon; LC 463 (Island Perimeter), LC 1254 (Closed Islands), LC 1568 (Minimum Days to Disconnect Island) are variations.

Shape E: topological sort via post-order

On a DAG, the reverse post-order of DFS gives a topological ordering. Run DFS from every unvisited node; on the way out of the recursion (after recursing into all children), push the node onto a stack. Reverse the stack at the end. This works because in post-order, a node is recorded only after all its descendants — ensuring it appears before none of its descendants in the reverse. Examples: LC 210 Course Schedule II, LC 269 Alien Dictionary.

Shape F: backtracking-flavoured DFS (with state)

DFS where you carry a partial solution down the recursion, extend it on entry, and undo the extension on the way back up. The "undo" step is what distinguishes backtracking from plain DFS. Used for enumeration: permutations (LC 46), combinations (LC 77), word search (LC 79), N-Queens (LC 51), Sudoku solver (LC 37). The mark/unmark on the visited set (or the constraint state) is the signature.

3 · Sister algorithms

DFS sits inside a small family of "exhaustive search" algorithms. Each cousin trades a different axis: IDDFS trades repeated work for memory; bidirectional search trades simplicity for asymptotic speedup; randomised DFS trades determinism for diversity. Knowing the family prevents reaching for plain DFS when the constraint rules it out.

• Iterative Deepening DFS (IDDFS). Run DFS with a depth limit of 1, then 2, then 3, and so on, until the goal is found. Wastes repeated work (the limit-3 call re-explores everything the limit-2 call did) but uses only O(depth) memory. Use it when (a) the branching factor is large enough that BFS's frontier blows memory, and (b) the depth of the answer is shallow relative to the depth of the tree. Standard in chess engines (iterative deepening with alpha-beta search), in AI route-finding with bounded budget, and in any "find any solution under a depth limit" task.
• Bidirectional search. When you have both a start and a goal, search from both ends simultaneously, alternating layers. The two frontiers meet in the middle. Worst case O(b^(d/2)) instead of O(b^d): a square-root speedup. Standard for word-ladder problems (LC 127 BFS variant), and used in maps routing where you can search forward from origin and backward from destination. Tricky to implement correctly (synchronising the two frontiers, detecting the meeting point, reconstructing the path through both halves).
• Randomised DFS for maze generation. A DFS where, at each node, you visit the neighbours in random order. Produces a spanning tree of the graph (a maze with no cycles). The classic algorithm behind procedurally-generated dungeon layouts in roguelikes. Variants (Wilson's algorithm, recursive division) trade different statistical properties of the resulting maze.
• Tarjan's strongly connected components. A single-pass DFS that identifies all SCCs of a directed graph in O(V + E) using "low-link" values. Generalises three-colour DFS — instead of just detecting cycles, it groups every node into its SCC. Used by compilers (cyclic type definitions), build systems (cyclic dependencies), and link analysis (PageRank's reducible-vs-irreducible component handling).
• Hierholzer's algorithm for Eulerian paths. A DFS that traverses every edge exactly once, when one exists (each vertex has even degree in the undirected case; in-degree = out-degree in the directed case). Used in LC 332 Reconstruct Itinerary. The trick: post-order accumulation of the path, then reverse — a DFS-with-stack idiom specifically tuned to edge traversal.
• DFS-with-memoisation = top-down dynamic programming. The boundary between DFS and DP is just the memoisation cache. The moment you cache subproblem answers in a hash map keyed on "state at this node", DFS becomes DP. LC 329 Longest Increasing Path in a Matrix is the cleanest example: written as DFS with a cache, it's also DP.

4 · Canonical example: Course Schedule (LC 207)

Problem. Given numCourses and a list of prerequisite pairs [a, b] meaning "must take b before a", return whether it's possible to finish all courses. Equivalent to: is the directed prerequisite graph acyclic?

Input:  numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]
Output: true   (linear chain, no cycle)

Input:  numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false  (cycle: 0 → 1 → 0)

Build the adjacency list, then DFS from every unvisited node, marking nodes as IN-PROGRESS while recursing and DONE on return. A back-edge (an edge to a node currently in IN-PROGRESS) is a cycle. This is the three-colour idiom: WHITE = unseen, GREY = on the current recursion stack, BLACK = fully explored.

5 · Reference implementation

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    # Adjacency: course → list of courses that depend on it
    adj = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        adj[b].append(a)

    WHITE, GREY, BLACK = 0, 1, 2
    color = [WHITE] * num_courses

    def dfs(u: int) -> bool:
        if color[u] == GREY:
            return False               # back-edge → cycle
        if color[u] == BLACK:
            return True                # already verified acyclic
        color[u] = GREY
        for v in adj[u]:
            if not dfs(v):
                return False
        color[u] = BLACK
        return True

    return all(dfs(i) for i in range(num_courses))

6 · Variations

7 · Five-problem progression

8 · Three more worked problems

Three problems chosen to exercise three different DFS shapes from Section 2. The reference implementation above (LC 207) covered the three-colour idiom; these add island counting on a grid (Shape D) and the Eulerian-path post-order trick (Shape E with a Hierholzer twist).

8a · LC 207: Course Schedule, revisited with the 3-state contract

A second pass at LC 207 to make the three-colour contract precise. The reference implementation above used Python; here is the Go version with explicit colour transitions and the back-edge test written as a return value, so the propagation rule is unambiguous.

func canFinish(numCourses int, prerequisites [][]int) bool {
    adj := make([][]int, numCourses)
    for _, p := range prerequisites {
        adj[p[1]] = append(adj[p[1]], p[0])
    }

    const (
        WHITE = 0 // unvisited
        GREY  = 1 // on the current DFS stack (in progress)
        BLACK = 2 // fully explored
    )
    color := make([]int, numCourses)

    var dfs func(u int) bool
    dfs = func(u int) bool {
        if color[u] == GREY {
            return false // back-edge -> cycle
        }
        if color[u] == BLACK {
            return true // already verified acyclic
        }
        color[u] = GREY
        for _, v := range adj[u] {
            if !dfs(v) {
                return false
            }
        }
        color[u] = BLACK
        return true
    }

    for i := 0; i < numCourses; i++ {
        if !dfs(i) {
            return false
        }
    }
    return true
}

8b · LC 200: Number of Islands

Problem. Given an m × n 2D grid of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Input:  [
  ['1','1','0','0'],
  ['1','1','0','0'],
  ['0','0','1','1'],
  ['0','0','1','1'],
]
Output: 2

Shape D in its purest form. Loop over every cell; whenever you find an unvisited '1', DFS-flood from it (mark all connected '1's as visited) and increment the island count. Mutating the grid in place ('1' → '0') is the cleanest way to mark visited without an extra set. But say "I'm mutating the input" out loud in an interview before doing so.

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    m, n := len(grid), len(grid[0])
    count := 0

    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1' {
            return
        }
        grid[r][c] = '0' // mark visited by sinking
        dfs(r-1, c)
        dfs(r+1, c)
        dfs(r, c-1)
        dfs(r, c+1)
    }

    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if grid[r][c] == '1' {
                count++
                dfs(r, c)
            }
        }
    }
    return count
}

8c · LC 332 (HARD): Reconstruct Itinerary (Hierholzer's Eulerian path)

Problem. Given a list of airline tickets where tickets[i] = [from, to], reconstruct the itinerary in order. All tickets belong to a man who departs from "JFK"; the itinerary must use all tickets once. If there are multiple valid itineraries, return the lexicographically smallest.

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

This is an Eulerian path problem: traverse every edge exactly once, starting at JFK. Hierholzer's trick: post-order DFS, accumulating the path on the way back. Then reverse the result at the end. Sort each node's adjacency list so the lexicographically smallest neighbour is always tried first.

import "sort"

func findItinerary(tickets [][]string) []string {
    // Build adjacency, each list sorted descending so we can pop() the smallest
    adj := map[string][]string{}
    for _, t := range tickets {
        adj[t[0]] = append(adj[t[0]], t[1])
    }
    for k := range adj {
        sort.Sort(sort.Reverse(sort.StringSlice(adj[k])))
    }

    var route []string
    var dfs func(node string)
    dfs = func(node string) {
        for len(adj[node]) > 0 {
            // Pop the lexicographically smallest neighbour (end of reverse-sorted list)
            n := len(adj[node])
            next := adj[node][n-1]
            adj[node] = adj[node][:n-1]
            dfs(next)
        }
        route = append(route, node) // POST-ORDER: add on the way out
    }

    dfs("JFK")

    // Reverse the route
    for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 {
        route[i], route[j] = route[j], route[i]
    }
    return route
}

9 · How to solve hard DFS problems, step-by-step

DFS rewards a few minutes of upfront thinking. Four questions to answer before writing the recursive function — they determine the signature, the base case, and whether you need backtracking.

Step 1: What state does the recursion carry?

Every recursive DFS function has a signature; the signature is the state. For "is X reachable", the only state is the current node. For "find any path from A to B", you carry the path-so-far. For N-Queens, you carry the partial board (or just the columns and diagonals used). The signature design decision is "what does the caller need to pass in for this call to make sense?". Get this wrong and you'll end up using global variables, which leak between calls and make backtracking impossible.

Step 2: What's the base case?

Three options: (a) you've found the answer (success: return / record). (b) You've hit a dead-end (failure: return without recording). (c) You've already visited this node (avoid revisit: return). Often two or three of these apply. Write them out as if statements at the top of the function before the recursion. The base case is where the recursion terminates; without it, you'll stack-overflow on the first cycle.

Step 3: Pure exploration or backtracking?

Pure exploration: mark visited and never look back. Used when "have I been here" is the only question (LC 200 Number of Islands, LC 207 Course Schedule). The visited set is global to the whole search.

Backtracking: mark on entry, recurse, unmark on exit. Used when you need to enumerate multiple paths through overlapping state space (LC 79 Word Search, LC 51 N-Queens). The visited set is effectively "the path so far"; on the way back up, you remove the current node so other paths can explore through it.

The distinguishing rule: do other valid solutions pass through this node? If yes, you need backtracking. If no, plain exploration suffices.

Step 4: Iterative or recursive?

Default to recursive; it reads top-down like the problem and is shorter. Switch to iterative (explicit stack) when:

• The graph depth can exceed your language's recursion limit (Python: ~1,000; Go: ~250k effective in most builds, but be careful with goroutines whose stacks start small).
• You need fine-grained control over the stack (e.g. early-termination from deep in the recursion without unwinding via exceptions).
• You're translating to a language without good tail-call optimisation, and the recursion is tail-recursive.

Iterative DFS uses a []Node slice as the stack: append to push, slice [:n-1] to pop. The only subtlety: when you push neighbours, push them in reverse order if you want them processed in the natural left-to-right order (because the stack pops in LIFO order).

10 · DFS exploration order on a small graph

A six-node directed graph, traversed by DFS starting at A. The numbers next to each node are the discovery time (when the node was coloured GREY); the order in which BLACK is assigned is the post-order.

The discovery times (d=1, d=2, ...) record when each node first turned GREY; that's the pre-order. The reverse of the order in which nodes finish (turn BLACK) is the topological sort — the classic way to compute it from DFS. Here, post-order is F, D, B, E, C, A; reversed, that's A, C, E, B, D, F, a valid topological ordering of the DAG.

11 · Common pitfalls: recursion depth, visited, mutating graphs

• Recursion depth blowing up. Python's default recursion limit is ~1000. A 10⁴-node graph in a linear chain crashes. Either raise the limit (sys.setrecursionlimit) or port to an iterative DFS.
• Forgetting to mark visited. On a cyclic graph, DFS loops forever. Even on a DAG, you'll re-explore subtrees exponentially.
• Two-colour cycle detection on a directed graph. Mis-reports cross-edges as cycles. Always use three-colour for directed graphs.
• Mutating the input. Tempting on grid problems ("set visited = '#'"), but destroys the input. Interviewers usually want non-destructive.
• Backtracking that forgets to undo. Mark on entry, unmark on exit. If you mark globally without undoing, you can't enumerate multiple paths.
• Building the result list inside the recursion. Pass the result by reference; don't return a list per call and try to concatenate. The copy cost is O(V) per node.
• Counting paths twice. Bidirectional edges in an undirected graph: track the parent to avoid going back the way you came.
• Recursion depth limit, in detail. Python's default is 1,000, easy to blow on a linked-list-as-tree or a deeply nested JSON. Go's effective limit is around 250,000 frames for the default stack (Go grows the stack dynamically, but you'll hit a memory or scheduler limit eventually). Java/Go default thread stacks handle ~10,000 frames before a typical SO. Rust on a 2 MB thread stack: ~50,000. If the input has any chance of exceeding 10⁴ depth, convert to an explicit stack. Recursive DFS will simply crash.
• Not marking visited causes infinite loop. The single most common DFS bug on cyclic graphs. The visited set must be checked at the top of the recursive function, before recursing. A correct shape: if visited[u] { return }; visited[u] = true; for v in adj[u] { dfs(v) }. Forgetting either the check or the mark, and you'll either loop forever or revisit subtrees exponentially.
• Modifying the graph during DFS. Tempting in problems that ask to "remove edges as they're traversed". But the recursion is currently inspecting adj[u]; mutating it under your feet via adj[u] = adj[u][:0] or similar can skip nodes or process them twice. The safe pattern: snapshot the adjacency list at the top of the call, iterate the snapshot, modify in a separate pass. The unsafe pattern triggers the dreaded "the bug only appears on inputs of size > 50" class of failure.
• Not restoring state in backtracking flavour. The backtracking step (mark on entry / unmark on exit) is symmetric. If you unmark in the wrong place (e.g. inside the for-loop instead of after), you're either restoring state too early (corrupting the current path) or too late (corrupting siblings' state). Rule: the mark and unmark live at the very start and very end of the recursive function, with nothing else between them at the same nesting level. The unmark is the LAST statement before returning.
• Adjacency list built backwards. Especially in cycle-detection problems with prerequisites: "a depends on b" can be encoded as adj[a] = [b] (a points to its dependencies) or adj[b] = [a] (b points to its dependents). Both are valid graphs, but DFS over one is not equivalent to DFS over the other. The cycle direction flips. Decide which encoding you want and stick with it; misencoding is silent.
• Iterative DFS that processes nodes in the wrong order. A stack pops in LIFO; if you want children processed left-to-right, you push them right-to-left. Forgetting to reverse-push gives mirror-image output. Doesn't matter for correctness of reachability or component-count, matters for any problem where the discovery order is the answer.

12 · Complexity, side by side

DFS and BFS share the same asymptotic time complexity, but their space and traversal properties diverge in ways that decide which one fits the problem.

13 · Traversal orders, in one diagram

The same DFS visit can produce three different orderings depending on when you record the node. Each is the right tool for a different class of problem.

# Three orderings, one traversal — only the print position changes.
def dfs(node):
    if node is None: return
    print(node)        # PRE-order
    dfs(node.left)
    # print(node)      # IN-order
    dfs(node.right)
    # print(node)      # POST-order

Pre-order serialises a tree: root, then recursively each subtree — used by JSON serialisation, tree copying, and prefix expression printing. In-order on a BST emits the elements sorted; this is the bridge between binary search trees and ordered iteration. Post-order processes children before parent — used to free a tree safely, evaluate an expression tree, and generate topological orderings.

14 · Real-world DFS, in production code

DFS isn't an algorithm interview question — it's the algorithm half the systems on your machine run constantly. Five places it shows up by name:

File-system traversal: find(1), du(1), git status.

The kernel's recursive directory walk is a textbook DFS, with the visited set replaced by inode-uniqueness. find . -type f is depth-first by default; reversing to BFS (find -depth) processes children before parent, which matters for rm -rf ordering.

Compiler dependency resolution.

npm, cargo, pip, go modules: every package resolver does a DFS over the dependency graph, detecting cycles with three-colour marking. The "cyclic dependency" error every developer has hit is the BLACK→GREY edge being caught.

HTML / XML parsers and the DOM.

Browser engines walk the DOM tree depth-first during layout and paint. document.querySelectorAll returns nodes in document order, which is a pre-order DFS. Removing a subtree from the DOM internally does a post-order walk to fire detachment events from the leaves up.

Web crawlers, in a controlled form.

Google's early crawlers were DFS, then BFS (better breadth, less hostile to sites), then a hybrid with priority. The visited set is a Bloom filter sized for billions of URLs.

Type-checkers and topological order.

TypeScript, Rust's borrow checker, Haskell's GHC: all do a post-order DFS over the type graph to type-check expressions bottom-up. The same machinery underlies build systems like Bazel and Make.

15 · What to say in the interview

1. "Reachability / components / cycle → DFS." Name the pattern. Specify directed vs undirected.
2. "Recursion or explicit stack." Mention both. Recursion is shorter; iterative is needed for very deep graphs.
3. "Visited set to avoid revisiting." Critical on cyclic graphs.
4. "For directed cycle detection, three-colour DFS." Articulate WHITE/GREY/BLACK and why two-colour isn't enough.
5. "Time O(V + E). Space O(V) for visited plus O(V) recursion stack." State both.
6. Edge cases. Empty graph, single node, self-loops, disconnected components, very deep linear chains (recursion limit).

16 · Where this gets asked

Specific companies hit DFS-shaped questions over and over. Names and what they tend to ask, from public Leetcode and Glassdoor breakdowns plus team-blog mentions:

17 · Try it yourself

Three problems, each one teaches a different DFS muscle. Spend 30 minutes on each before checking the hint — the struggle is where the pattern internalises.

Number of Islands · LC 200

The canonical grid-DFS. Iterate every cell; if it's land and unvisited, DFS-flood it and bump the count. The whole solution is 15 lines. Hint: a single visited set works, but mutating the grid in-place to '0' is cleaner.

Course Schedule · LC 207

The cycle-detection canon. Build the prereq graph, three-colour DFS, return false on any GREY→GREY edge. Hint: this is also doable via Kahn's algorithm (topological-sort BFS); doing it both ways teaches when each wins.

Word Search · LC 79

DFS with backtracking: your first time mixing the two. Pick a starting cell, walk the word letter-by-letter, undo the visit on the way back. Hint: the four-direction loop is the same in every grid problem; pre-define dirs = [(0,1),(0,-1),(1,0),(-1,0)] and reuse it.

Stretch: Critical Connections · LC 1192

Tarjan's bridge-finding algorithm. A serious DFS extension that introduces "low-link" — the smallest discovery time reachable from a subtree. Hint: the moment to attempt this is after you've done the three above blindfolded; it teaches the deepest DFS variant you'll see in interviews.

Further reading

• CLRS — Chapter 22. The three-colour scheme is from here; the formal treatment is worth reading once.
• Sedgewick & Wayne — Algorithms, Chapter 4. Cleaner code than CLRS; same content.
• Adjacent: BFS. The other half of graph traversal.
• Adjacent: Topological sort. Post-order DFS gives you topological order for free.
• Adjacent: Backtracking. DFS plus mark/unmark, the enumeration pattern.
• Semicolony: Algorithm visualiser. Step through DFS and watch the order of node visits.