LeetCode Visualizer
How it worksAll visualizations

Step by step · Python

Depth-first search, visualized step by step

Depth-first search follows one path as far as it goes, then backs up to the most recent fork and tries the next branch. Written recursively, the call stack does the remembering.

How it works
Python
graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["E"],
    "D": ["F"],
    "E": ["F"],
    "F": [],
}

visited = set()
order = []


def dfs(node):
    if node in visited:
        return
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        dfs(neighbor)


dfs("A")
print(order)

How depth-first search works

dfs(node) returns straight away if the node was already visited. Otherwise it marks and records the node, then calls itself on each neighbour in turn. A call only returns once everything reachable from it has been explored, and that is what produces the backtracking.

The example is a small directed graph: A → B, C; B → D; C → E; D → F; E → F. From A it visits A, B, D, F, backs all the way up to A, then goes down C to E — where F has already been visited.

What to watch for when it runs

  1. The call stack holds the current path from A, so its height is how deep the search has gone.
  2. When a branch is exhausted, frames pop one at a time — that is the backtracking, made visible.
  3. Compare the visit order with breadth-first search: one path to the end first, not one layer at a time.

Time and space complexity

Time
O(V + E)
Space
O(V)

Every vertex is visited once and every edge followed once. In the worst case — a long chain — the recursion is V calls deep.

Related visualizations

Stuck on your own version?

Paste it into the visualizer and watch your own code run, line by line — bugs included.