Depth-first search

graphtreestackrecursion

Follow one path as deep as it goes, then back up to the most recent branch not yet tried. A stack holds the branches still to try, and a visited set keeps cycles from looping forever.

How to get there

Go deep, remember the way back

1. State the job. Visit every node reachable from a start node, each exactly once. The graph is an adjacency list: graph[node] lists the node’s neighbors.

2. Walk it by hand and find where you get stuck. Take the graph with edges A–B, A–C, B–D, B–E, C–F, E–F, and from A always step to the first neighbor not yet seen: A, B, D. D’s only neighbor is B, already seen, so the walk hits a dead end. It has to continue from the most recent node that still has an untried neighbor: B, which still has E.

3. Find what to remember. The neighbors still to try, newest first, since a dead end sends the walk back to the most recent branch. Last in, first out is a stack: push a node’s neighbors when it is visited, and pop to choose the next node.

4. Stop the cycles. A, B, E, F, C leads back to A. Without memory the walk would go round forever, so keep a visited set and skip any node already in it.

5. Make the stack walk like the hand walk. Push the neighbors in reverse, so the first one listed comes off first. And a node can sit on the stack twice: A pushes C, and later F pushes C again. So check visited when a node is popped, and skip it if an earlier copy was already taken.

6. Check the cost. Each node is visited once and each adjacency list is read once: O(V + E) time. The visited set takes O(V) space, and the stack can hold up to one entry per edge end, O(E).

The reusable recipe: when one branch must be finished before the next one starts, keep the branches still to try on a stack. When the structure can loop back on itself, keep a visited set.

Let the stack's meaning write the loop

Variable	Always means, at the top of the loop
`stack`	nodes found but not yet taken, the most recently found on top; a node may appear twice
`visited`	the nodes already taken
`order`	the taken nodes, in the order they were taken

Code	What happened	What it keeps true
`stack = [start]`	nothing is taken yet	the start is the only node found
`node = stack.pop()`	the most recently found node comes off	the walk goes deeper before it goes wider
`if node in visited: continue`	an earlier copy of the node was already taken	each node enters `order` once
`visited.add(node)`, `order.append(node)`	the node is taken	`visited` and `order` both gain it
`for neighbor in reversed(graph[node]):`	its neighbors are found	pushed in reverse, the first one listed is popped next
`if neighbor not in visited: stack.append(neighbor)`	a neighbor not yet taken	it waits on the stack
`return order`	the stack is empty	every node reachable from `start` is in `order`

Why mark at pop, not at push. Marking a node when it is pushed keeps duplicates off the stack, but it claims the node for whichever node saw it first, not for the path that reaches it deepest. With edges A–B, A–C, A–D, B–D, the recursive walk goes A, B, D, C. Marking at push goes A, B, C, D, because A already claimed D before B could reach it. Marking at pop keeps the order identical to dfs_recursive.py.

The method carries over: write down what the stack holds, then each line either takes a node off it or puts the newly found ones on.

On a binary tree

A tree is a graph with no cycles, so every node is reached by exactly one path, from its parent. In the explainer’s tree example, the graph lists each parent as a neighbor, and the parent is the only neighbor visited ever skips.

A binary tree in LeetCode stores only left and right children, so the walk can never step back to a parent, and the visited set goes away. The recursion is three lines: take the node, walk its left subtree, walk its right subtree. That is dfs_tree.py.

Where the node’s own work goes names the order:

Order	The node is handled	On 1 with children 2, 3, and 2 with children 4, 5
preorder	before both subtrees	1, 2, 4, 5, 3
inorder	between the subtrees	4, 2, 5, 1, 3
postorder	after both subtrees	4, 5, 2, 3, 1

Postorder is what a depth or a subtree sum needs: a node’s answer is built from its children’s answers, which are ready only once both subtrees are done.

The reusable recipe: on a tree, drop the visited set and recurse into the children, and choose pre-, in- or postorder by when the node’s own work can happen.

Alternatives compared

Approach	Time	Space	How it works
Recursion (`dfs_recursive.py`)	O(V + E)	O(V)	The call stack holds the path back: each call visits its node, then calls itself on each neighbor not yet visited.
Explicit stack (`dfs_graph.py`)	O(V + E)	O(V + E)	A list used as a stack holds the nodes still to try; nodes are marked when popped.
Breadth-first search	O(V + E)	O(V)	The same loop with a queue: it reaches the same nodes, nearest first.

Recursion is the shortest to write, but each step deeper is one more call, and Python stops at 1,000 calls by default: a path of 10,000 nodes raises RecursionError. The explicit stack has no such limit.

Pick depth-first search when the answer depends on whole paths or whole subtrees: tree depths and sums, cycle detection, connected components, and backtracking through choices. Pick breadth-first search when the answer is about distance, such as the fewest steps from the start.

dfs_graph.py

def dfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = set()
    order = []
    stack = [start]

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)

    return order

dfs_recursive.py

def dfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = set()
    order = []

    def visit(node: str) -> None:
        visited.add(node)
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visit(neighbor)

    visit(start)
    return order

dfs_tree.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
def preorder(root: TreeNode | None) -> list[int]:
    order = []

    def visit(node: TreeNode | None) -> None:
        if not node:
            return
        order.append(node.val)
        visit(node.left)
        visit(node.right)

    visit(root)
    return order