Depth-First Search (DFS)

Question 1

What data structure is implicitly used in recursive DFS?

Accepted Answer

Stack — Recursion uses the Call Stack to track function calls, thus DFS behaves like a Stack-based traversal.

Question 2

DFS explores a graph by…

Accepted Answer

Going as deep as possible along a branch — Depth-First Search follows one path to its end, then backtracks to explore alternatives — naturally expressed with recursion or an explicit stack.

Question 3

What structure underlies DFS?

Accepted Answer

A stack — LIFO order produces the dive-then-backtrack behavior; recursion uses the call stack implicitly.

Question 4

What is DFS's time complexity on an adjacency list?

Accepted Answer

O(V + E) — Each vertex and edge is processed once, so DFS is O(V + E) with an adjacency list.

Question 5

DFS is the foundation of which ordering of a DAG?

Accepted Answer

A topological sort ordering — Pushing vertices onto a stack as their DFS finishes (postorder) and reversing yields a valid topological order of a DAG.

Question 6

To detect a cycle in a DIRECTED graph with DFS, you track…

Accepted Answer

Nodes currently sitting on the recursion stack — A back edge to a node still on the recursion stack (in-progress) signals a directed cycle; a plain visited set isn't enough.

Question 7

In an UNDIRECTED graph, DFS detects a cycle when it finds a visited neighbor that…

Accepted Answer

Is not the current node's immediate parent — Reaching an already-visited node other than where you came from means there's an alternate path forming a cycle.

Question 8

DFS finds STRONGLY connected components using algorithms like…

Accepted Answer

Tarjan's or Kosaraju's algorithm — Tarjan's uses low-link values in one DFS; Kosaraju's uses DFS on the graph then its transpose — both O(V+E) for SCCs.

Question 9

What is the space complexity of recursive DFS?

Accepted Answer

O(V) worst case for the full recursion stack — A long path makes the recursion as deep as O(V); very deep graphs can overflow the call stack, motivating an explicit stack.

Question 10

Articulation points and bridges (critical nodes/edges) are found via…

Accepted Answer

Via node discovery times and low-link ancestor values — Tracking each node's DFS discovery time and the lowest reachable ancestor (low-link) identifies cut vertices and bridges in O(V+E).

Depth-First Search (DFS)

Recursion Call Stack (LIFO)

Go deep first

Test your knowledge

What data structure is implicitly used in recursive DFS?

Write the code

Number of Islands

Example Cases

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?