DSA sheet · Graphs · Traversal pattern (DFS)

DFS Traversal of a Graph

The second traversal. The question and the graph are the same as in BFS (Problem 3), but now we must go deep first: from a node, pick one neighbour and keep going down that path until you get stuck, then come back and try the next neighbour. The teacher writes it with recursion and explains it through the call stack. At the end she shows the one line that makes the difference between BFS and DFS. DFS is the base of islands, provinces, all-paths, cycle detection and topological sort, so this page matters a lot.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · DFS with recursion (the teacher's solution)
• Part B · The same DFS with an explicit stack (no recursion limit)
• Part C · BFS vs DFS: the one difference
• Part D · Revision page

Part 0 · Before starting

Graph words used on this page

• Node (vertex) and edge: points, and lines joining two points. V = number of nodes, E = number of edges.
• Undirected: an edge (0)—(2) can be walked both ways. Directed: (0)→(2) only one way. Weighted: the edge has a cost written on it; with no number, the cost is 1.
• Adjacency list: adj[u] = list of u's neighbours. This question gives it to us. From an edge list we'd build it with adj[u].append(v); adj[v].append(u) for each edge (see Problem 3).
• Visited array: one True/False per node, so we never process a node twice and never loop forever around a cycle.
• Connected components: the separate pieces of a graph. This question promises one piece (connected), so one DFS from 0 reaches everything.

Recursion and the call stack, in 4 lines

• When a function calls itself, the current call pauses and waits on the call stack.
• The new call runs on top. When it finishes (returns), it is removed, and the paused call continues from the exact line where it stopped.
• Each call has its own local variables. Here, each call is identified by its node, and its for loop remembers which neighbour it reached.
• So the call stack automatically remembers "where to come back to". That is exactly what going deep and then coming back needs.

BFS (queue, level by level) was Problem 3. Grids as graphs, with 4 directions, start in Problem 6.

Part A · DFS with recursion

GFG: "DFS of Graph"

1The question in simple words

You get a connected, undirected graph with V nodes (0 … V−1) as an adjacency list. Start at node 0 and return the nodes in depth-first order, taking each node's neighbours left to right as listed in adj.

               (0)
             /  |  \
          (2)  (3)  (1)
           |   / \    \
          (4)(5) (6)  (7)

adj[0] = [2, 3, 1]     adj[4] = [2]
adj[1] = [0, 7]        adj[5] = [3]
adj[2] = [0, 4]        adj[6] = [3]
adj[3] = [0, 5, 6]     adj[7] = [1]

Expected: [0, 2, 4, 3, 5, 6, 1, 7]. Compare BFS on the same graph: [0, 2, 3, 1, 4, 5, 6, 7].

2What the constraints tell us

• 1 ≤ V ≤ 10⁴ and the graph is connected: node 0 always exists, so there's no empty case. A linear O(V + E) solution is far below the ~10⁸ operations limit.
• Values are node numbers up to 10⁴ → a normal int.
• Python-only warning: the recursion can be as deep as V. If the graph is a straight line 0–1–2–…–9999, the call stack holds 10⁴ calls. Python's default recursion limit is about 1000, so we must raise it (Part A code) or use an explicit stack (Part B).

3Intuition: walk a maze with one hand on the wall

Stand at 0. You have three corridors: 2, 3, 1. Take the first one, 2. Don't look at 3 and 1 yet. From 2, take its first new corridor, 4. From 4 there's nowhere new to go: a dead end. Walk back to 2 (nothing new there either), back to 0, and only now take the next corridor, 3. And so on.

The teacher sees the result as paths from the start: 0 → 2 → 4, then 0 → 3 → 5 and 3 → 6, then 0 → 1 → 7. Each path is followed all the way down before the next one starts.

Nodes like 4, 5, 6, 7 have no new neighbours; she calls them leaf nodes, like in a tree. But a graph with a cycle may have no leaves at all. There you would go round and round forever, which is why we need the visited array.

4Building the logic step by step

Step 1: what does the function need? (the teacher's checklist)

In BFS everything lived in one loop. Here we call a function again and again, and a function only knows what it is given. So she lists what each call needs:

• node: the node this call is standing on. Every call is about one node, and that is what tells the calls on the stack apart.
• ans: the shared answer list, so every call can add its node.
• adj: to find the node's children.
• visited: to know which nodes are already done.

Step 2: what is the base case?

Every recursion needs a way to stop. BFS stopped when the queue was empty. The teacher asks: what do we do the moment we are on a node? Two things, before leaving for the children, because once we go deeper we won't be "standing" here again:

1. add the node to ans (just node, not node.val: a graph node here is simply an int);
2. mark visited[node] = True, so nobody comes here again.

Step 3: go to the children, but only one at a time

Loop over adj[node]. In BFS, we pushed every child into the queue in this loop. In DFS we take one child and call the function on it straight away. The rest of the loop waits, paused on the stack, until that whole branch is finished.

Step 4: the bug when we don't check visited

Say we call DFS on every child without checking. dfs(0) → dfs(2). Node 2's children are [0, 4], so it calls dfs(0) again → 0 is added to ans a second time, which calls dfs(2) again… We'd go back and forth along the edge 0–2 forever. Every node must be printed once, and from 2 we want to go on to 4, not back to 0.

Step 5: start, and the size of visited

adj has one sub-list per node (index 0 = children of 0, …, index 7 = children of 7), so V = len(adj) = 8, and visited = [False] * 8. The main function calls the helper with 0 because the question says "start from vertex 0". If it said start from 1, we'd pass 1. When the helper is done, ans is full, and we return it. The visited array was only a helper; nobody asks for it.

5Approach steps

1. V = len(adj); visited = [False] * V; ans = [].
2. Call dfs(0).
3. Inside dfs(node): mark it visited and append it to ans.
4. For every neighbour in adj[node], left to right: if not visited, call dfs(nei) and wait for it to finish.
5. When the loop ends, the call returns by itself. After the first call returns, return ans.

6Code (Python)

import sys

class Solution:
    def dfs(self, adj):
        sys.setrecursionlimit(max(1000, 2 * len(adj) + 100))   # depth can reach V
        n = len(adj)
        visited = [False] * n
        ans = []
        self.go(0, adj, visited, ans)    # the question says: start at 0
        return ans

    def go(self, node, adj, visited, ans):
        visited[node] = True             # never come back here
        ans.append(node)                 # do the node's work first
        for nei in adj[node]:            # children, left to right
            if not visited[nei]:
                self.go(nei, adj, visited, ans)   # go deep; the loop waits
        # loop finished: every child is done, so return to the caller

7Code line by line

8Dry run with the call stack

1. go(0): mark 0, ans = [0]. Children [2, 3, 1]: 2 is unvisited → call go(2). go(0) waits at "child 2".
2. go(2): mark 2, ans = [0,2]. Children [0, 4]: 0 is visited, skip. 4 is new → call go(4).
3. go(4): mark 4, ans = [0,2,4]. Children [2]: visited. The loop ends → go(4) returns and leaves the stack.
4. Back in go(2): its loop has no more children → returns.
5. Back in go(0): next child 3 is new → go(3): mark, ans = [0,2,4,3]. Children [0, 5, 6]: 0 visited; 5 new → go(5): ans = [0,2,4,3,5]. Its only child 3 is visited → returns.
6. go(3) continues: 6 is new → go(6): ans = […,5,6]. Child 3 visited → returns. go(3)'s loop is over → returns.
7. go(0) continues: last child 1 is new → go(1): ans = […,6,1]. Children [0, 7]: 0 visited; 7 new → go(7): ans = […,1,7]. Child 1 visited → returns. go(1) returns.
8. go(0) has run its loop over all 3 children → returns. The stack is empty. Answer [0, 2, 4, 3, 5, 6, 1, 7] ✓

The newest call is on top (red). go(0) stays at the bottom the whole time, because it can only finish after all three of its branches are done.

        (0✓)
      /  |   \
   (2✓) (3)  (1)
    |   / \     \
  (4✓)(5) (6)  (7)

        (0✓)
      /  |   \
   (2✓) (3✓) (1)
    |    / \     \
  (4✓)(5✓)(6✓) (7)

Compare with BFS: after its first round, BFS had already marked 2, 3 and 1. DFS hasn't touched 3 or 1 at all until the 2-branch is completely finished.

9Complexity & remember

• Time O(V + E): each node gets exactly one call (visited stops a second one), and each call scans its neighbour list once. All lists together hold 2E entries for an undirected graph. The teacher says "O(N)" because every node is visited once; the neighbour scans add the E part.
• Space O(V): visited (V) + ans (V) + the call stack, which the teacher points out as the extra cost of recursion. It is as deep as the longest chain of waiting calls: up to V for a line-shaped graph.

Part B · The same DFS with an explicit stack

This part is not in the video. It is here because Python's recursion limit is a real trap, and because "DFS = a stack" is something interviewers like to ask. The question, constraints and answer are the same as Part A. Only the way we remember the pending work changes: our own list used as a stack, instead of Python's call stack.

1Intuition

A stack is last in, first out. If we push a node's neighbours and then pop, we get the most recently found node next, so we keep going deeper, just like recursion. Two details make the order match Part A exactly:

1. Push the neighbours in reverse. The stack gives back the last thing pushed. To visit adj[0] = [2, 3, 1] in the order 2, 3, 1, we push 1, 3, 2, so 2 sits on top.
2. Mark when popping, not when pushing. A node can sit in the stack more than once; when it's popped a second time we simply skip it.

2Approach steps

1. Push 0 onto the stack.
2. While the stack is not empty: pop a node. If it's already visited, skip it.
3. Otherwise mark it and append it to ans.
4. Push its unvisited neighbours in reverse order.

3Code (Python)

class Solution:
    def dfs(self, adj):
        n = len(adj)
        visited = [False] * n
        ans = []
        stack = [0]                          # a Python list used as a stack
        while stack:
            node = stack.pop()               # the most recent node
            if visited[node]:
                continue                     # an old copy, already done
            visited[node] = True             # mark when popped
            ans.append(node)
            for nei in reversed(adj[node]):  # reversed: first child ends on top
                if not visited[nei]:
                    stack.append(nei)
        return ans

4Dry run (first few steps)

The stack holds the same "waiting branches" the call stack held in Part A: after step 2, [1, 3] are the branches of 0 still to do.

5Complexity & remember

• Time O(V + E): every neighbour list is scanned once (when its node is first popped); each push is matched by one pop, and there are at most 2E + 1 pushes.
• Space O(V + E) in the worst case for the stack (duplicate copies), with no recursion-limit problems.

Part C · BFS vs DFS: the one difference

The teacher puts the two codes side by side. Both do the same things at a node: record it, mark it, look at its children. The difference is what happens inside the children loop:

Her test: if you call the function from inside the children loop, it is DFS; if you clear the whole children list into a queue first, it is BFS. Which one to use depends on the question. From the patterns video: BFS for "fewest steps / nearest / level-wise", DFS for "explore all paths / connectivity / go deep before backtracking". The coming problems will train this choice.

Part D · Revision page

adj = [[2, 3, 1], [0, 7], [0, 4], [0, 5, 6], [2], [3], [3], [1]]
print(Solution().dfs(adj))                       # [0, 2, 4, 3, 5, 6, 1, 7]
print(Solution().dfs([[1, 2], [0, 2, 3], [0, 1], [1]]))   # [0, 1, 2, 3]
print(Solution().dfs([[]]))                      # [0]
line = [[1]] + [[i - 1, i + 1] for i in range(1, 9999)] + [[9998]]
print(Solution().dfs(line)[-3:])                 # [9997, 9998, 9999]

Based on this video: DFS Traversal of Graph