Depth First Search

Depth-First Search (DFS) is more than just a graph traversal technique. It is a fundamental recursive exploration strategy used to systematically explore all possible paths in a problem’s state space. DFS appears naturally in scenarios such as navigating mazes, resolving task dependencies, detecting cycles, and exploring decision trees.

In technical interviews at companies like Google, Amazon, and Meta, DFS is a core algorithm. Interviewers use it to assess your understanding of recursion, your ability to reason about call stacks, and your comfort with backtracking-based problem solving.

Mastering DFS helps you move beyond surface-level traversal and develop the mindset needed to solve complex search and exploration problems.

What is Depth First Search?

Depth First Search also known for short as DFS is a traversal algorithm used to explore nodes in a graph or tree. The defining idea of DFS is simple:

DFS prioritizes depth over breadth, which is what fundamentally differentiates it from Breadth-First Search (BFS).

Intuition behind DFS

Imagine you are exploring a dark maze. To make sure you don’t get lost, you carry a ball of string and tie the end at the entrance.

You choose one hallway and walk forward, following it as far as it goes. If you hit a dead end, you do not restart from the entrance. Instead, you retreat along the rope to the most recent junction where another unexplored path exists, and then continue from there.

This strategy ensures that every path is explored fully to its end before moving on to alternatives. That is exactly how DFS behaves.

Key characteristics

• The goal: It is a method for exploring a network or a map to ensure every single point is checked.
• The memory: It keeps track of its path using a “last-visited” memory system, always focusing on the very last place it reached before looking anywhere else.
• The strategy: It follows a “Deep-Dive” rule. It prioritizes moving forward as far as possible into a single path rather than checking all immediate options at once.

How DFS works

At its core, DFS follows a simple process. DFS relies on a “visited” set to ensure it doesn’t get stuck in an infinite loop if the graph has cycles.

Step-by-step algorithm

1. Initialization: Start at the source node. Mark it as visited and push it onto the stack.
2. Iterate/Recurse: While the stack is not empty:
   1. Pop the top node from the stack (or move to the next recursive call).
   2. For every unvisited neighbor of this node:
      1. Mark it as visited.
      2. Push it onto the stack.
3. If no unvisited neighbors exist: This is where you return to the previous node. Pop the current node off the stack to return to the previous node and check its remaining neighbors.
4. Termination: The process continues until the stack is empty, meaning every reachable node has been explored.

DFS can be implemented using recursion, where the system call stack naturally move to the previous nodes, or iteratively using an explicit stack to simulate the same behavior.

Python implementation

DFS can be implemented recursively (cleaner) or iteratively (avoids stack overflow for very deep graphs).

Recursive approach

In a recursive implementation, the call stack manages the traversal automatically. Each recursive call explores a deeper node, and returning from the function corresponds to backtracking (retreating back to the parent/previous node). This approach is concise and closely mirrors the conceptual definition of DFS, making it easier to reason about.

The key requirement in a recursive DFS is maintaining a record of visited nodes. Without this, the algorithm may revisit nodes indefinitely in graphs that contain cycles.

def dfsRecursive(graph, node, visited=None):
    # Initialize the visited set on the first call
    # This set is shared across all recursive calls to prevent infinite loops
    if visited is None:
        visited = set()

    # Mark the current node as visited so we don't process it again
    visited.add(node)
    print(f"Visited: {node}")

    # Retrieve neighbors from the adjacency list.get(node, []) ensures 
    # the code doesn't crash if a node has no neighbors
    for neighbor in graph.get(node, []):
        # The 'Depth' focus: If a neighbor hasn't been seen, 
        # immediately dive into that branch before checking other neighbors
        if neighbor not in visited:
            dfsRecursive(graph, neighbor, visited)


graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("DFS Recursive Starting from Node A:")
dfsRecursive(graph, 'A')

Iterative DFS (using an explicit stack)

An iterative DFS implementation replaces recursion with an explicit stack. Instead of relying on function calls, nodes are pushed onto and popped from the stack manually. This approach gives more control over memory usage and avoids issues such as stack overflow when dealing with very deep graphs.

Although the implementation details differ, the underlying logic remains the same: nodes are explored deeply before alternatives are considered.

def dfsIterative(graph, startNode):
    # 'visited' ensures we don't process the same node twice (prevents infinite loops)
    visited = set()
    
    # We use a standard Python list as a Stack (LIFO: Last-In, First-Out)
    # Start by pushing the initial node onto the stack
    stack = [startNode]
    
    while stack:
        # Pop the most recently added node (diving deeper)
        node = stack.pop()
        
        # A node might be added to the stack multiple times before it's visited
        if node not in visited:
            print(f"Visited: {node}")
            visited.add(node)

            # Retrieve neighbors; use reversed() to maintain the same 
            # visiting order as the recursive version (left-to-right)
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    # Push unvisited neighbors onto the stack to be explored next
                    stack.append(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("DFS Starting from Node A:")
dfsIterative(graph, 'A')

Dry run example of iterative DFS

Let’s look at the following illustration to get a better understanding of the solution:

1 / 6

Complexity analysis

Understanding the cost of DFS is crucial for optimization.

Time complexity: O(V + E)

• V = Number of Vertices (Nodes).
• E = Number of Edges (Connections).
• Reason: We visit every node once and explore every edge once.

Space complexity: O(V)

Reason: In the worst-case scenario (a graph that is essentially one long line), the recursion stack will hold all V nodes.

Where DFS is used in real-world applications

Depth First Search appears frequently in problems that involve exploration, recursion, or hierarchical structures. It is widely used for traversing trees, exploring graphs, detecting cycles, finding connected components, and performing topological sorting.

DFS is also a natural fit for solving puzzles, navigating mazes, and implementing backtracking algorithms, including:

1. Traversing trees: DFS is the core logic used to perform pre-order, in-order, and post-order traversals.
2. Graph traversal: Moving through complex networks to find connectivity.
3. Finding connected components: Identifying “islands” of nodes in social networks or map data.
4. Detecting cycles: Vital in compiler design and resource allocation to prevent deadlocks.
5. Topological sorting: Determining the correct order of tasks or dependencies.
6. Solving puzzles: Exploring all possible states in games like sudoku or mazes.

DFS vs. BFS

Choosing the right traversal depends on your goal.

Common pitfalls while using DFS

One of the most common mistakes when implementing DFS is failing to track visited nodes. In graphs that contain cycles, this can cause the algorithm to revisit the same nodes repeatedly, resulting in infinite loops.

Other frequent issues include:

• Stack overflow due to deep recursion: Recursive DFS can exceed the call stack limit when applied to very deep or highly skewed graphs.
• Incorrect assumptions about shortest paths: DFS may find a valid path, but it does not guarantee the shortest path, which can lead to incorrect solutions if applied without care.

Another common oversight is handling disconnected graphs. If DFS is started from only a single node, some components may remain unvisited.

• Incomplete traversal of disconnected graphs: To ensure full coverage, DFS must be initiated from each unvisited node rather than relying on a single starting point.