DFS Interview Questions

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. What a DFS question is actually testing

DFS questions are not about traversal. Any candidate can walk a graph. What is being checked is whether you know the bookkeeping DFS makes available and BFS does not: the order things finish in, whether a vertex is still on the stack, and how far back a subtree can reach.

That is the whole subject. Cycle detection, topological sort, strongly connected components, bridges and articulation points are all one traversal plus one extra array. If a question asks about ordering, dependencies, cycles, or what breaks if this is removed, it is a DFS question. If it asks for the fewest of anything, it is a BFS question.

The eight below are the ones that recur, each with the problem, the solution, the follow-up, and the error that loses the offer. Every worked example was executed by script.

2. The template, recursive and iterative

Recursive DFS is four lines, and you should be able to write it without thinking.

def dfs(u, adj, seen):
    seen.add(u)
    for v in adj[u]:
        if v not in seen:
            dfs(v, adj, seen)

The iterative version is where candidates slip, because the obvious translation is subtly different from the recursive one.

def dfs_iter(src, adj):
    seen, stack = set(), [src]
    while stack:
        u = stack.pop()
        if u in seen:            # a vertex can be pushed several times
            continue
        seen.add(u)
        for v in adj[u]:
            if v not in seen:
                stack.append(v)

Two things to notice, and to say out loud.

• Check seen on pop, not only on push. Unlike BFS, the same vertex can sit on the stack more than once, pushed by several neighbours before any is expanded. Skip the pop-time check and you get duplicate visits.
• The visit order differs from the recursive version. Neighbours pushed in ascending order pop in descending order, so iterative DFS explores the last neighbour first. Push them reversed to match. A favourite gotcha.

The harder point: the plain iterative version has no post-order. It knows when a vertex is discovered, never when its subtree finishes, and finish time is exactly what sections 5, 9 and 10 need. To recover it, push each vertex twice or carry a child index in the frame. Knowing recursion is not merely cosmetic here is worth saying.

The technique is old: it is Trémaux's rule for threading a maze, recorded by Lucas in 1882.

3. Cycle detection in a directed graph

The question. Does a directed graph contain a cycle? Phrased as deadlock detection, build dependency loops, or "can this course schedule be completed".

The wrong answer is a single visited set: reaching a seen vertex does not mean a cycle, it may be a second route into a finished part of the graph. The right answer uses three colours: white undiscovered, grey discovered but still on the recursion stack, black finished.

WHITE, GREY, BLACK = 0, 1, 2

def has_cycle(adj, n):
    colour = [WHITE] * n

    def visit(u):
        colour[u] = GREY
        for v in adj[u]:
            if colour[v] == GREY:      # back edge: v is an ancestor
                return True
            if colour[v] == WHITE and visit(v):
                return True
        colour[u] = BLACK              # only now is u finished
        return False

    return any(colour[s] == WHITE and visit(s) for s in range(n))

An edge into a grey vertex is a back edge, and a directed graph has a cycle if and only if a DFS finds a back edge. An edge into a black vertex is harmless. That equivalence, and the four-way classification of edges it belongs to, is the standard treatment in Cormen, Leiserson, Rivest and Stein.

On the running graph, DFS from vertex 0 classifies its 8 arcs as 5 tree edges, 1 forward edge and 2 cross edges, with no back edge, so it is acyclic. Add the single arc 5 → 0 and exactly one back edge appears.

The follow-up: print the cycle, not just a boolean. The back edge gives it to you: if it is u → v, walk parent pointers from u up to v and close the loop. Here the back edge is 5 → 0 and the cycle is 0 → 1 → 3 → 5 → 0. A parent array costs one line and turns a yes/no into the diagnosis a real build tool has to report.

The trap. Setting colour[u] = BLACK in the wrong place, or not at all. Leave finished vertices grey and every second route into them looks like a cycle, so you report false positives on any DAG containing a diamond, as the running graph does.

4. Cycle detection in an undirected graph

The question. Same problem, undirected graph. It looks like the previous question and it is not.

Three colours are wrong here. Every undirected edge is traversable both ways, so stepping from u to v, the edge back to u looks like an edge into a grey vertex, and every edge reports a cycle. Instead, ignore the edge you arrived on.

def has_cycle_undirected(adj, n):
    seen = [False] * n

    def visit(u, parent):
        seen[u] = True
        for v in adj[u]:
            if not seen[v]:
                if visit(v, u): return True
            elif v != parent:          # a seen, non-parent neighbour
                return True
        return False

    return any(not seen[s] and visit(s, -1) for s in range(n))

Without the v != parent guard, a graph consisting of the single edge 0-1 reports a cycle. With it, a 4-vertex tree correctly reports none and a triangle correctly reports one. Those are the three test cases to check on the whiteboard, and checking them unprompted reads very well.

The follow-up: parallel edges? Then v != parent is not enough: two distinct edges between u and v genuinely form a cycle of length 2, and the parent check swallows the second. Track the edge you came in on, not the vertex. See simple graphs vs multigraphs.

The trap. A disconnected graph. The outer loop over every unvisited vertex is not optional, and a solution that starts only at vertex 0 passes every connected test case.

5. Topological sort by post-order

The question. Order the vertices of a DAG so every arc points forward. The BFS answer is Kahn's in-degree peeling; the DFS answer is shorter and is what a DFS question wants.

Run DFS, append each vertex when it finishes, reverse the list. That is the whole algorithm, and the reason is one sentence: a vertex finishes only after everything reachable from it, so it finishes later than its successors, and reversing puts it before them.

def topological_sort(adj, n):
    colour = [0] * n           # 0 white, 1 grey, 2 black
    order = []

    def visit(u):
        colour[u] = 1
        for v in adj[u]:
            if colour[v] == 1: raise ValueError("cycle")
            if colour[v] == 0: visit(v)
        colour[u] = 2
        order.append(u)        # post-order: AFTER the children

    for s in range(n):
        if colour[s] == 0: visit(s)
    return order[::-1]

On the running DAG the post-order is 5, 3, 1, 4, 2, 0; reversing gives 0, 2, 4, 1, 3, 5, and all eight arcs point forward in it. Say that it is a topological order, not the one: a DAG usually has many.

The follow-up: how do you detect a cycle here? The grey check from section 3. That is the appeal: one traversal both orders the DAG and rejects a non-DAG, where Kahn's needs a separate count at the end. The DFS formulation is Tarjan's.

The trap. Appending in pre-order, when the vertex is discovered rather than when it finishes. The result looks plausible, is wrong, and on small graphs often coincides with a valid order, so it survives casual testing.

6. Clone graph

The question. Given a reference to a node in a connected undirected graph, return a deep copy.

The only difficulty is cycles: a naive recursive copy loops forever. The fix is a map from original node to its copy, which doubles as the visited set, and it must be written before recursing.

def clone_graph(node, made=None):
    if node is None: return None
    if made is None: made = {}
    if node in made:
        return made[node]
    copy = Node(node.val)
    made[node] = copy              # register BEFORE recursing
    for nb in node.neighbors:
        copy.neighbors.append(clone_graph(nb, made))
    return copy

Registering the copy before the recursive calls is the entire question. Do it after and a cycle sends you round again before the entry exists, recursing until the stack dies. It is the same shape as memoising any self-referential structure.

The follow-up: iterative, or BFS? Both work, with an identical map. Say that the map, not the traversal order, is what makes it correct. O(V + E) either way.

7. All paths: DFS as backtracking

The question. List every path from a source to a target in a DAG. Variants: all root-to-leaf paths, path sum, permutations.

This is the family where DFS stops being a graph traversal and becomes backtracking, and the difference is one line: you undo your choice on the way out.

def all_paths(adj, src, dst):
    out, path = [], []

    def walk(u):
        path.append(u)
        if u == dst:
            out.append(path[:])    # COPY, not the live list
        else:
            for v in adj[u]:
                walk(v)
        path.pop()                 # the backtracking step

    walk(src)
    return out

On the running DAG there are exactly 4 paths from 0 to 5: 0→1→3→5, 0→2→3→5, 0→2→4→5 and 0→3→5.

Two details carry the answer. Append a copy, path[:], since path is mutated afterwards and the reference gives you a list of identical empty lists. And there is no visited set: you enumerate paths, not vertices, so a vertex legitimately appears in many paths. The path.pop() keeps state correct without one.

The follow-up: complexity? Not O(V + E). A DAG can have exponentially many paths, so listing them is exponential in the output; the honest answer is O(V × 2V). Saying linear here reveals you have not thought about what the output is. Asked only how many paths exist, that is a different problem: count with dynamic programming over the topological order, in O(V + E).

The trap. Adding a visited set because "DFS always has one". On a cyclic graph you do exclude vertices already on the current path, but that is the path, not a global set, and a global set silently returns a subset of the answers.

8. Word search on a grid

The question. Given a grid of letters and a word, decide whether the word can be spelled by moving between orthogonally adjacent cells, using no cell twice.

This is backtracking on an implicit grid graph, and the "no cell twice" clause is what forces the undo.

def exist(board, word):
    R, C = len(board), len(board[0])

    def walk(r, c, i):
        if i == len(word): return True
        if not (0 <= r < R and 0 <= c < C): return False
        if board[r][c] != word[i]: return False

        board[r][c] = '#'                      # mark, so the path cannot reuse it
        found = any(walk(r + dr, c + dc, i + 1)
                    for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)))
        board[r][c] = word[i]                  # UNDO on the way out
        return found

    return any(walk(r, c, 0) for r in range(R) for c in range(C))

The marker must be restored: a cell blocked by one failed attempt has to be available to a different start, and forgetting it gives a function that succeeds only when the first path tried happens to work. Overwriting the board instead of keeping a visited set is a legitimate trick, but say so, since it mutates the caller's input.

The follow-up: complexity. O(R × C × 3L) for a word of length L: every cell is a possible start, and after the first step you never go back the way you came, so each later step has at most 3 choices, not 4. That 3 is the detail that signals you thought about it.

9. Strongly connected components

The question. Partition a directed graph into maximal sets of mutually reachable vertices. It appears as "find circular dependencies", or as preprocessing before a DAG algorithm.

Two DFS answers exist and you should know which you are writing.

Kosaraju-Sharir is two passes and far easier to get right under pressure. DFS the graph recording finish order, then DFS the reversed graph taking vertices in decreasing finish order; each tree of the second pass is one component.

def kosaraju(adj, radj, n):
    seen, order = [False] * n, []
    def pass1(u):
        seen[u] = True
        for v in adj[u]:
            if not seen[v]: pass1(v)
        order.append(u)                  # finish order
    for s in range(n):
        if not seen[s]: pass1(s)

    comp, c = [-1] * n, 0
    def pass2(u):
        comp[u] = c
        for v in radj[u]:
            if comp[v] == -1: pass2(v)
    for u in reversed(order):            # decreasing finish time
        if comp[u] == -1:
            pass2(u); c += 1
    return comp, c

On a graph of two triangles, 0→1→2→0 and 3→4→5→3, joined by the single arc 2→3, this returns exactly two components, {0,1,2} and {3,4,5}. Reachability confirms it: 0 reaches 3, and 3 does not reach 0.

Tarjan's algorithm does it in one pass with a stack and a low-link value: faster in practice, much easier to botch on a whiteboard. Both are O(V + E), and both have a visualizer here. Tarjan's 1972 paper gave the single-pass method; the two-pass version is credited to Kosaraju and was first published by Sharir in 1981.

The follow-up: why does the reversed graph work? Reversing every arc leaves the components unchanged, since mutual reachability is symmetric. The vertex with the highest finish time lies in a source component of the condensation, and reversal turns a source into a sink, so a DFS started there cannot leave it.

10. Bridges and articulation points

The question. Which edges, if removed, disconnect the graph? Which vertices? Framed as single points of failure, or critical connections in a cluster.

This is the deepest standard DFS question, and it is one idea: alongside each vertex's discovery time, track low[u], the smallest discovery time reachable from u's subtree using at most one non-tree edge.

def bridges(adj, n):
    disc, low = [-1] * n, [-1] * n
    out, clock = [], 0

    def visit(u, parent):
        nonlocal clock
        disc[u] = low[u] = clock; clock += 1
        for v in adj[u]:
            if v == parent:
                parent = -2                 # skip ONE copy of the parent edge
                continue
            if disc[v] == -1:
                visit(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    out.append((u, v))      # nothing below v reaches u or above
            else:
                low[u] = min(low[u], disc[v])

    for s in range(n):
        if disc[s] == -1: visit(s, -1)
    return out

low[v] > disc[u] says the subtree below v has no way back to u or above, so u-v is the only route and removing it splits the graph. On the two-triangle graph the discovery times run 0 to 5 and the low values are 0, 0, 0, 3, 3, 3. The only bridge is 2-3; the articulation points are 2 and 3. Brute force agrees: removing that edge, or either vertex, leaves 2 components, and no other single removal disconnects anything.

Articulation points use the same traversal, two rules: a non-root u qualifies if some child v has low[v] >= disc[u], and the root qualifies if it has more than one DFS child. Note >= against the > for bridges. That one character separates the two answers, and mixing them up is the commonest error here.

The trap. The parent check. if v == parent: continue without the one-shot guard is wrong on a multigraph: two parallel edges to the parent mean the pair is not a bridge, and skipping both hides it. Track the edge index, or skip only the first occurrence as above. The algorithm is Hopcroft and Tarjan's, 1973, and there is a visualizer for it.

11. Complexity, and the recursion depth question

Every algorithm above is one traversal, so the time bound barely moves. Space is where the interesting question lives.

The recursion depth question is asked in almost every DFS interview, so have the answer ready. DFS recurses as deep as the longest path it follows, which on a path graph is V. CPython's default limit is 1000, so a few thousand vertices in a line crashes it, and a 1000 by 1000 grid of land cells can recurse a million deep.

The fix is the iterative version from section 2, not sys.setrecursionlimit, which only turns a clean exception into a real stack overflow. Say that explicitly. The O(V) space is that stack, and the honest comparison with BFS is that DFS holds one root-to-leaf path while BFS holds a whole layer: neither is uniformly smaller, it depends on whether the graph is deep or wide. Aho, Hopcroft and Ullman give the aggregate analysis; Sedgewick and Wayne the shortest clear treatment.

12. Mistakes that fail the interview

Ordered by frequency; the first three account for most rejected solutions.

• One visited set for directed cycle detection. Seeing a vertex again is not a cycle. Grey (on the stack) must be distinct from black (finished), or every DAG with two routes to a vertex reports one.
• Using three colours for undirected cycle detection. The reverse error. Every edge looks like a back edge unless you skip the one you arrived on.
• Recursing on input that can be large. A million-cell grid recurses a million deep. Offer the iterative version before being asked.
• Building the topological order in pre-order. It must be post-order, appended when the vertex finishes, then reversed. Pre-order produces something that looks like an answer and is not.
• Forgetting to undo in backtracking. The path.pop(), or restoring the grid cell. Without it the first failed branch poisons every later one.
• Storing the live list instead of a copy. out.append(path) gives a list of references to one mutated list. It must be path[:].
• Confusing > and >= in the low-link test. low[v] > disc[u] is a bridge, >= is an articulation point. One character apart.
• Omitting the outer loop over components. Cycle detection, component counting and SCC all need DFS restarted from every unvisited vertex.
• Not asking about the input. Directed or undirected? Connected? Self-loops or parallel edges? Each changes the code, and Skiena's point holds: problems are won in the modelling.

The habit that prevents most of these: before writing, name the extra array. Colour, parent, finish order, or low-link. DFS questions differ from each other by that array, not by the traversal, and naming it first makes the rest mechanical. McDowell makes the same argument generally; it is unusually literal here.

14. References

The papers that introduced these techniques and the texts that analyse them, in chronological order.

1. Lucas, É. (1882). Récréations Mathématiques, Volume 1. Gauthier-Villars. (Records Trémaux's systematic maze-threading rule, the earliest description of depth-first search.)
2. Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms.” SIAM Journal on Computing, 1(2), 146–160.
3. Hopcroft, J. and Tarjan, R. E. (1973). “Algorithm 447: efficient algorithms for graph manipulation.” Communications of the ACM, 16(6), 372–378.
4. Aho, A. V., Hopcroft, J. E. and Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.
5. Tarjan, R. E. (1976). “Edge-disjoint spanning trees and depth-first search.” Acta Informatica, 6(2), 171–185.
6. Sharir, M. (1981). “A strong-connectivity algorithm and its applications in data flow analysis.” Computers & Mathematics with Applications, 7(1), 67–72.
7. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms, 3rd edition, Section 22.3. MIT Press.
8. Sedgewick, R. and Wayne, K. (2011). Algorithms, 4th edition, Sections 4.1–4.2. Addison-Wesley.
9. McDowell, G. L. (2015). Cracking the Coding Interview, 6th edition. CareerCup.
10. Skiena, S. S. (2020). The Algorithm Design Manual, 3rd edition, Chapter 5. Springer.