Depth First Search

Interviewer cue: “does a path exist”, “how many connected groups”, “flood-fill this region”, or “is there a cycle” — depth-first search goes as deep as possible down one branch before backtracking, making it the natural fit for exploring whether something exists rather than how far away it is.

What you’ll learn

The recursive DFS template, using the call stack for you.
The iterative version with an explicit stack — same order, no recursion-depth risk.
Connected components / flood fill, the pattern behind Number of Islands and Max Area of Island.
A quick preview of cycle detection on a directed graph (Course Schedule).

The pattern (recursive)

dfs_recursive.py

def dfs(graph, node, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)   # go deep before trying siblings
    return order
 
 
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2, 4],
    4: [3],
}
 
print("DFS order from 0:", dfs(graph, 0))

dfs_recursive.py

def dfs(graph, node, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)   # go deep before trying siblings
    return order
 
 
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2, 4],
    4: [3],
}
 
print("DFS order from 0:", dfs(graph, 0))

The pattern (iterative, with an explicit stack)

dfs_iterative.py

def dfs_iterative(graph, start):
    visited = {start}
    stack = [start]
    order = []
 
    while stack:
        node = stack.pop()             # LIFO: most recently pushed goes first
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
 
    return order
 
 
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2, 4],
    4: [3],
}
 
print("DFS order from 0 (iterative):", dfs_iterative(graph, 0))

dfs_iterative.py

def dfs_iterative(graph, start):
    visited = {start}
    stack = [start]
    order = []
 
    while stack:
        node = stack.pop()             # LIFO: most recently pushed goes first
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
 
    return order
 
 
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2, 4],
    4: [3],
}
 
print("DFS order from 0 (iterative):", dfs_iterative(graph, 0))

How it works

diagram DFS visit order from node 0 (goes deep before wide) mermaid

  graph TD
    N0["0 (#1)"] --- N1["1 (#2)"]
    N0 --- N2["2 (#4)"]
    N1 --- N3["3 (#3)"]
    N2 --- N3
    N3 --- N4["4 (#5)"]

From 00, DFS commits to 11 immediately, then to 11’s unvisited neighbor 33, then to 33’s unvisited neighbor 22 — only backtracking to explore 44 once that entire branch is exhausted. Compare this to BFS’s diagram in the previous lesson: same graph, completely different visit order.

Worked example: connected components / flood fill

Counting islands means: for every unvisited land cell, run a DFS that marks its entire connected region as visited, then count how many times you had to start a fresh DFS.

dfs_flood_fill_islands.py

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    visited = set()
 
    def flood_fill(r, c):
        stack = [(r, c)]
        visited.add((r, c))
        while stack:
            row, col = stack.pop()
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and grid[nr][nc] == 1 and (nr, nc) not in visited):
                    visited.add((nr, nc))
                    stack.append((nr, nc))
 
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in visited:
                islands += 1          # found a NEW island's starting cell
                flood_fill(r, c)
 
    return islands
 
 
grid = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1],
]
print("number of islands:", count_islands(grid))

dfs_flood_fill_islands.py

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    visited = set()
 
    def flood_fill(r, c):
        stack = [(r, c)]
        visited.add((r, c))
        while stack:
            row, col = stack.pop()
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and grid[nr][nc] == 1 and (nr, nc) not in visited):
                    visited.add((nr, nc))
                    stack.append((nr, nc))
 
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in visited:
                islands += 1          # found a NEW island's starting cell
                flood_fill(r, c)
 
    return islands
 
 
grid = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1],
]
print("number of islands:", count_islands(grid))

A preview: cycle detection

Course Schedule asks “can all courses be finished given prerequisites?” — equivalently, “does this directed graph have a cycle?” DFS answers this by tracking three states per node: unvisited, currently on this DFS path, and fully finished. A cycle exists exactly when you reach a node that’s still on the current path.

dfs_cycle_detection_teaser.py

WHITE, GRAY, BLACK = 0, 1, 2   # unvisited, currently exploring, fully done
 
 
def can_finish(num_courses, prerequisites):
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in prerequisites:
        graph[prereq].append(course)
 
    state = [WHITE] * num_courses
 
    def has_cycle(node):
        state[node] = GRAY                  # mark "on the current DFS path"
        for neighbor in graph[node]:
            if state[neighbor] == GRAY:
                return True                  # back edge to a node still on the path -> cycle
            if state[neighbor] == WHITE and has_cycle(neighbor):
                return True
        state[node] = BLACK                  # fully explored, safe forever
        return False
 
    return not any(state[i] == WHITE and has_cycle(i) for i in range(num_courses))
 
 
print(can_finish(2, [[1, 0]]))          # True: 0 -> 1, no cycle
print(can_finish(2, [[1, 0], [0, 1]]))  # False: 0 -> 1 -> 0, a cycle

dfs_cycle_detection_teaser.py

WHITE, GRAY, BLACK = 0, 1, 2   # unvisited, currently exploring, fully done
 
 
def can_finish(num_courses, prerequisites):
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in prerequisites:
        graph[prereq].append(course)
 
    state = [WHITE] * num_courses
 
    def has_cycle(node):
        state[node] = GRAY                  # mark "on the current DFS path"
        for neighbor in graph[node]:
            if state[neighbor] == GRAY:
                return True                  # back edge to a node still on the path -> cycle
            if state[neighbor] == WHITE and has_cycle(neighbor):
                return True
        state[node] = BLACK                  # fully explored, safe forever
        return False
 
    return not any(state[i] == WHITE and has_cycle(i) for i in range(num_courses))
 
 
print(can_finish(2, [[1, 0]]))          # True: 0 -> 1, no cycle
print(can_finish(2, [[1, 0], [0, 1]]))  # False: 0 -> 1 -> 0, a cycle

Complexity

Recursive or iterative, DFS visits every node and edge at most once: $O(V + E)$ time. Space is $O(V)$ for the visited set, plus $O(V)$ in the worst case for the recursion stack (or explicit stack) on a graph that degenerates into one long chain.

When to use it

Connected components / flood fill — islands, regions, clusters.
Path existence — “can you get from A to B”, without needing the shortest route.
Cycle detection — directed graphs (course prerequisites, deadlock detection) via the 3-state trick above.
Exhaustive exploration with undo — the very next pattern, backtracking, is DFS plus “undo the last choice before trying the next one.”

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 797 — All Paths From Source to Target · Medium

Problem. Given a DAG as an adjacency list of nn nodes, return all paths from node 00 to node n - 1n - 1, in any order.

Constraints. 2 <= n <= 152 <= n <= 15, the graph is acyclic and has no self-loops.

Examples. [[1,2],[3],[3],[]][[1,2],[3],[3],[]] gives [[0,1,3],[0,2,3]][[0,1,3],[0,2,3]]

Editorial

This is backtracking on a graph rather than pure traversal: you are enumerating paths, not visiting nodes once.

Time $O(2^n \times n)$ in the worst case — a complete DAG has exponentially many paths, and the constraint n <= 15n <= 15 tells you that is expected. Space $O(n)$ for the recursion and path.

The absence of a visited set is deliberate, and it is the detail worth understanding. In ordinary traversal you mark nodes to avoid revisiting. Here a node may legitimately lie on many different paths — node 33 appears in three of the second example’s five paths — so marking it would lose answers. The DAG guarantee is what makes omitting it safe: with no cycles, the recursion cannot loop forever.

The usual backtracking disciplines still apply: record list(path)list(path) not pathpath, and pair every appendappend with a poppop.

Follow-ups: “What if the graph had cycles?” — infinite paths; you would need a per-path visited set (added and removed alongside the path) to avoid revisiting within the current path. “Just count the paths?” — DP over the DAG, $O(V + E)$ , no enumeration. “Only the shortest path?” — BFS. “Why is exponential acceptable?” — the output itself is exponential.

LC 841 — Keys and Rooms · Medium

Problem. nn rooms are locked except room 00. Each room contains keys to other rooms. Return TrueTrue if you can visit all rooms starting from room 00.

Constraints. 2 <= n <= 10002 <= n <= 1000, keys are valid room numbers, no key to room 00.

Examples. [[1],[2],[3],[]][[1],[2],[3],[]] gives TrueTrue · [[1,3],[3,0,1],[2],[0]][[1,3],[3,0,1],[2],[0]] gives FalseFalse (room 2 is unreachable)

Editorial

“Can I reach everything from one node?” is answered by a single traversal plus a count. Either DFS or BFS works — there is no distance question, so the choice is arbitrary.

Time $O(V + E)$ — every room entered once, every key examined once. Space $O(V)$ .

The seenseen check does double duty: it prevents re-traversal and it makes the final count meaningful. Rooms can contain keys to rooms you have already opened — room 1 in the second example holds a key to room 0 — so without it the loop would never terminate.

The second example returns FalseFalse because room 2’s only key holder is room 2 itself: nothing reachable from room 0 provides it.

This is connected-component counting specialised to “is there exactly one component containing node 0, and does it cover everything”.

Follow-ups: “Which rooms are unreachable?” — return set(range(n)) - seenset(range(n)) - seen. “Iterative or recursive?” — either; the explicit stack avoids Python’s recursion limit at n = 1000n = 1000. “What if room 0 were locked too?” — the answer would be FalseFalse unless n == 0n == 0. “Minimum keys to open everything?” — a much harder covering problem.

LC 1443 — Minimum Time to Collect All Apples in a Tree · Medium

Problem. An undirected tree has nn nodes rooted at 00. Each edge takes 1 second to traverse in each direction. Return the minimum seconds to collect all apples and return to node 00.

Constraints. 1 <= n <= 10^51 <= n <= 10^5, edgesedges forms a tree, hasApplehasApple has length nn.

Examples. With edges [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]][[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]] and apples at nodes 2, 4, 5, the answer is 88; with apples at 2 and 5 only, 66; with no apples, 00

Editorial

Because it is a tree, any edge you traverse downward must also be traversed back up — so each useful edge costs exactly 22. The question is which edges are useful.

An edge to child cc is worth taking exactly when there is an apple at or below cc. The recursion expresses that as sub > 0 or hasApple[nxt]sub > 0 or hasApple[nxt]: a non-zero subtree cost means an apple lies deeper, and hasApple[nxt]hasApple[nxt] covers an apple at the child itself.

Time $O(n)$ . Space $O(n)$ for the adjacency list plus $O(h)$ recursion.

This is the Tree DFS “return a summary upward” shape, with the summary being a cost and the pruning condition doing the real work.

Two practical notes:

Pass the parent down. The edge list is undirected, so without it the recursion immediately walks back up and loops.
Recursion depth. At n = 10^5n = 10^5 a path-shaped tree exceeds Python’s default limit; mention sys.setrecursionlimitsys.setrecursionlimit or an iterative post-order.

An apple at the root costs nothing extra, which the no-apples case (00) and the structure of the condition both reflect — the root is never a “child” of anything.

Follow-ups: “Not required to return to the root?” — subtract the longest downward path to an apple, since that final ascent is saved. “Weighted edges?” — multiply by the weight instead of using 2. “Collect only kk apples?” — much harder, a tree-DP over counts.

LeetCode problem set

#	Problem	Difficulty	The twist
200	Number of Islands	Medium	(DFS variant) — the flood-fill pattern above
695	Max Area of Island	Medium	Flood fill, returning a size instead of just counting
133	Clone Graph	Medium	DFS while building a copy, using a `visitedvisited` map from original node to its clone (so cycles in the graph don’t infinite-loop you)
112	Path Sum	Easy	DFS down a tree, subtracting each node’s value from a running target
207	Course Schedule	Medium	The 3-state cycle-detection preview above

Recap

Recursive DFS uses the call stack; iterative DFS uses an explicit listlist as a stack — same visit order either way.
stack.pop()stack.pop() (LIFO) is the one-line difference from BFS’s queue.popleft()queue.popleft() (FIFO).
Flood fill = DFS that marks an entire connected region visited in one call; counting how many times you start a new one counts components.
Cycle detection on a directed graph needs 3 states (unvisited/on-path/done), not just a plain visited set.
$O(V + E)$ time, $O(V)$ space.

Next: Backtracking — DFS that also undoes each choice, for generating every valid arrangement instead of just checking reachability.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Depth First Search

What you’ll learn

The pattern (recursive)

The pattern (iterative, with an explicit stack)

How it works

Worked example: connected components / flood fill

A preview: cycle detection

Complexity

When to use it

Practice — real LeetCode problems

LC 797 — All Paths From Source to Target · Medium

LC 841 — Keys and Rooms · Medium

LC 1443 — Minimum Time to Collect All Apples in a Tree · Medium

LeetCode problem set

Recap

Was this page helpful?