What is DFS traversal? Depth-first search step by step

In this article

1. Before you start
2. Why interviewers ask this
3. DFS traversal from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

DFS is the walk underneath a large share of graph and tree questions, so a candidate who can trace it can reason about islands in a grid, dependency orders, cycles and tree paths. Questions arrive as "traverse this graph", "count the connected regions" or "why did your solution crash on a long input". A weak answer writes the recursive code from memory and cannot say what it returns for a disconnected graph. A strong answer names the visited set, gives the running time and explains what happens when the path is very long. The three-part answer to practise is: the visit rule, the cost, the two failure cases. This page builds each part from zero.

DFS traversal from first principles

Depth-first search

Depth-first search is a graph traversal that, from the current node, moves to an unvisited neighbour and repeats, going as deep as possible before it backs up to try the next neighbour.

Call stack

The call stack is the memory region in which a running program keeps one frame for each function call that has started and not yet finished.

In plain words

Think of exploring a maze with a ball of string. You walk down a corridor and keep choosing a path you have not tried. At a dead end you wind the string back to the last junction. You take the next unused path there. You are done when the string is back at the start. The analogy breaks in one place. A maze has one entrance. A graph may have several separate regions, and one ball of string never reaches the others.

In one precise sentence: DFS marks the current node, visits each unmarked neighbour in turn by repeating itself on that neighbour, and returns when all neighbours are marked. Sedgewick and Wayne describe it as a classic recursive method for systematically examining each of the vertices and edges in a graph.

Step 1: Mark the start node as visited

The first move is to record that the start node has been reached. Put the node in the visited set and, if you are listing nodes in visit order, append it to the list. The input is a graph stored as an adjacency list, which maps each node to the list of its neighbours, plus a start node. The output so far is a visited set with one entry.

Do this before looking at any neighbour, not after. If you mark late, a cycle can bring you back to a node that is still being processed and the search never ends. The example graph here has eight nodes A to H and seven edges: A-B, A-C, B-D, B-E, C-F, E-F and G-H.¹ Starting at A, the visited set becomes {A}. What you now know: marking first is what makes cycles safe.

Step 2: Go one level deeper at each unvisited neighbour

Look at the neighbours of the current node in a fixed order and, for the first one not in the visited set, run the same procedure on it. With neighbours sorted alphabetically, A has neighbours B and C, so DFS goes to B, then from B to D, because D comes before E.

Each such call marks its node and then looks at its own neighbours, so the search keeps going deeper rather than looking at C yet. The order in which nodes are first reached is the traversal order. On the example the order from A begins A, B, D.¹ The nodes waiting to be finished are held on the call stack, one frame per node on the current path. What you now know: the path from the start to the current node is exactly the stack.

Step 3: Backtrack when no unvisited neighbour remains

When every neighbour of the current node is already visited, the function returns, which takes the search back one step along the path. At D the only neighbour is B, which is visited, so D finishes and control returns to B. B then tries its next neighbour, E, and from E the search reaches F and then C.

Backtracking is not a separate instruction. It is the return of the recursive call, and the stack frame of the finished node disappears. The full order from A is A, B, D, E, F, C, which is what the recursive code prints.¹ Each node records an entry time when it is first reached and an exit time when it finishes; here A enters at 1 and exits at 12, and D enters at 3 and exits at 4. The Competitive Programming (CP) Algorithms article, last updated May 2026 uses these times to test ancestry in constant time. What you now know: a node is finished only when all its neighbours are visited.

Step 4: Restart from every node not yet visited

After the first call returns, some nodes may still be unvisited: they are in a different connected component. A connected component is a group of nodes joined to each other but not to the rest. A full traversal loops over every node and starts a new DFS from each one that is not visited.

This is the line candidates forget. A search from A alone visits 6 nodes and ends, while G and H are never seen. The restart loop begins a second search at G, which reaches H, so the whole graph is covered by two searches, and the number of searches equals the number of connected components, here 2.¹ The same loop is how you count islands in a grid or regions in a network. What you now know: one start covers one component, and a loop covers the graph.

Step 5: Swap the recursion for an explicit stack when the path is long

Recursion uses the call stack, and the call stack is limited. The Python documentation says the recursion limit prevents infinite recursion from crashing the interpreter and warns that setting it too high can crash Python. In our run the default limit was 1,000 frames, a recursive DFS on a path of 500 nodes worked, and on a path of 5,000 nodes it raised a RecursionError.¹

The fix is an explicit stack: a list you push neighbours onto and pop from. Push the start node; then repeatedly pop a node, skip it if visited, mark it, and push its unvisited neighbours in reverse order so the first neighbour is popped first. Sedgewick and Wayne raise the same stack-overflow risk and set a non-recursive version as an exercise. The explicit-stack version visits the example in the same order and handled the 5,000-node path.¹ After A and B are popped, the stack holds C, E and D with D on top, so D is visited next. What you now know: recursion and an explicit stack are the same algorithm with different bookkeeping.

1 · Mark A2 · Go deeper3 · Backtrack4 · Restart5 · StackReplay

Step-by-step description

1. Mark the start node A as visited.
2. A to B, then B to D, the first neighbours in order.
3. D is finished, so B goes on to E, F and C; A-C is a back edge.
4. G was never reached, so a second search covers G and H.
5. An explicit stack gives the same order without recursion.

• DFS marks a node as soon as it is reached.
• DFS runs in time proportional to nodes plus edges.
• A restart loop covers every connected component.

Worked example

On the eight-node graph the recursive search, the explicit-stack search and the loop over all nodes give the results below. Everything in the table was produced by the script, not typed by hand.¹

Text description of the diagram

• A search from A alone visits 6 nodes.
• The restart loop visits all 8 nodes.

Each undirected edge is examined once from each end, so the 7 edges cause 14 checks and the 8 nodes are each marked once.¹ That is the running time: time proportional to V plus E, written O(V + E), where V is the number of nodes (also called vertices) and E is the number of edges.

Sedgewick and Wayne state that DFS marks all the vertices connected to a source in time proportional to the sum of their degrees, and CP-Algorithms gives the same bound as O(m + n), with n nodes and m edges. The edge A-C is a back edge: C reaches A, which is a visited ancestor, and this is how DFS notices a cycle. CP-Algorithms also proves that on an undirected graph every edge DFS meets is a tree edge or a back edge.

The whole routine is short:

def dfs_all(adj, nodes):
    visited, order = set(), []
    def go(u):
        visited.add(u)                 # mark first
        order.append(u)
        for w in adj[u]:
            if w not in visited:
                go(w)                  # go deeper; return = backtrack
    for n in nodes:                    # restart loop for disconnected graphs
        if n not in visited:
            go(n)
    return order

Trade-offs and edge cases

DFS versus breadth-first search (BFS). BFS visits nodes level by level using a queue; DFS goes deep using a stack. From A the BFS order on the example is A, B, C, D, E, F, against A, B, D, E, F, C for DFS.¹ CP-Algorithms notes that DFS finds shortest paths in a tree but not on general graphs, so use BFS when you need the fewest edges between two nodes in an unweighted graph and DFS when you need to explore everything, find components, order tasks or check for cycles.

Text description of the diagram

• From A the DFS order is A, B, D, E, F, C.
• From A the BFS order is A, B, C, D, E, F.

Depth limits. Recursive DFS needs stack space proportional to the longest path it follows, so a long chain such as a linked list or a path-shaped graph is the worst case; use the explicit stack or raise the limit with care.

Order is not unique. Visit order depends on the order in which neighbours are listed. Two correct implementations can print different orders, so a checker should accept any valid DFS order or fix the neighbour order in the problem.

Directed graphs add a third state. On a directed graph a node that has been reached but not finished is "in progress"; an edge to an in-progress node is a cycle. The detect-cycle article and the topological sort article build on exactly this idea.

How to answer it in an interview

The spoken structure is: the visit rule and the visited set, the cost, then the two failures, a disconnected graph and a deep path.

Common mistakes

"Start DFS at node 0 and you have visited the graph." (wrong) Only the component that contains the start is reached. (right) "I loop over every node and start a search from each unvisited one."

"Mark a node when you finish it." (wrong) A cycle returns to a node still in progress and the search never ends. (right) "I mark a node as soon as I reach it."

"DFS finds the shortest path." (wrong) It finds a path, not the shortest one on a general graph. (right) "For fewest edges I use BFS."

"Recursion is always fine." (wrong) Depth equals path length, so a long chain breaks the default limit. (right) "I use an explicit stack when the depth can be large."

Follow-up questions

What is the time complexity of DFS?

O(V + E) with an adjacency list: each node is marked once and each edge is checked from both ends, 14 checks for the 7 edges here.¹ Recursive DFS needs O(V) extra space. The explicit-stack version on this page can hold one entry per edge end, O(E), and peaked at 19,702 entries on a 200-node complete graph.¹ Pushing one neighbour iterator per node instead keeps the stack at O(V).

When should you use DFS instead of BFS?

Use DFS to explore everything: components, islands, cycle checks and orderings of dependencies. Use BFS for fewest steps in an unweighted graph. Recursive DFS holds one path, not a whole level, so it can use less memory than BFS on wide graphs.

How do you do DFS without recursion?

Push the start node on a stack, then repeat: pop a node, skip it if visited, mark it and push its unvisited neighbours in reverse order. The example gives A, B, D, E, F, C, the same as the recursive order.¹

What if the graph is one very long path?

Recursive DFS needs one stack frame per node. In our run 5,000 nodes raised a RecursionError against a default limit of 1,000.¹ Use an explicit stack. See monotonic stack for another stack pattern, and lowest common ancestor and binary tree vertical order traversal for tree walks that rely on the same traversal ideas.

How does DFS detect a cycle?

In an undirected graph, an edge to a visited node that is not the parent you came from is a back edge and closes a cycle; the example has one, A-C. In a directed graph it must point to a node still in progress.

Sources

1. Algorithms, 4th edition, section 4.1 Undirected Graphs — Princeton University (Sedgewick and Wayne), 16 Apr 2019
2. Depth First Search — CP-Algorithms, 24 May 2026
3. sys: System-specific parameters and functions (setrecursionlimit) — Python Software Foundation (Python 3 documentation), 24 Oct 2026