DEV Community

Cover image for Converting Recursive Depth-First Search (DFS) to an Iterative Approach in Java
Aditya Pratap Bhuyan
Aditya Pratap Bhuyan

Posted on

Converting Recursive Depth-First Search (DFS) to an Iterative Approach in Java

Converting a recursive Depth-First Search (DFS) to an iterative version involves replacing the inherent function call stack used in recursion with an explicit stack data structure. This helps avoid potential stack overflow errors and can provide better control over the traversal process.

How to Convert Recursive DFS to Iterative DFS in Java:

  1. Understand the Recursive DFS Structure A typical recursive DFS looks like this:
   void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
       visited[node] = true;
       // Process the node here (e.g., print or accumulate)
       for (int neighbor : graph.get(node)) {
           if (!visited[neighbor]) {
               dfs(neighbor, visited, graph);
           }
       }
   }
Enter fullscreen mode Exit fullscreen mode
  1. Replace Recursion with an Explicit Stack

    Use a Stack<Integer> to manually manage nodes to visit.

  2. Standard Iterative DFS Algorithm:

   void iterativeDFS(int start, List<List<Integer>> graph) {
       boolean[] visited = new boolean[graph.size()];
       Stack<Integer> stack = new Stack<>();
       stack.push(start);

       while (!stack.isEmpty()) {
           int node = stack.pop();

           if (!visited[node]) {
               visited[node] = true;
               // Process the node here (e.g., print or accumulate)
               System.out.println("Visited node: " + node);

               // Push neighbors to stack (usually in reverse order to maintain traversal order)
               List<Integer> neighbors = graph.get(node);
               for (int i = neighbors.size() - 1; i >= 0; i--) {
                   int neighbor = neighbors.get(i);
                   if (!visited[neighbor]) {
                       stack.push(neighbor);
                   }
               }
           }
       }
   }
Enter fullscreen mode Exit fullscreen mode

Key Points:

  • Stack Usage: Instead of recursive calls, the stack stores nodes waiting to be visited.
  • Visited Check: You must mark nodes as visited after popping them to avoid revisiting.
  • Ordering Neighbors: To maintain the same node visitation order as recursive DFS, neighbors should often be pushed onto the stack in reverse order.
  • Graph Representation: Here, the graph is represented as an adjacency list (List<List<Integer>>).

Has This Been Seen in Practice?

Yes, iterative DFS is a common technique in professional software development, especially:

  • When the graph is very deep or large, and recursion depth could cause stack overflow.
  • In coding interviews, iterative DFS is frequently requested as an alternative to recursion.
  • In system-level applications where manual stack management improves performance or control.

This iterative approach is widely used and well-understood as a key graph traversal strategy in Java and other languages.

Warp.dev image

The best coding agent. Backed by benchmarks.

Warp outperforms every other coding agent on the market, and gives you full control over which model you use. Get started now for free, or upgrade and unlock 2.5x AI credits on Warp's paid plans.

Download Warp

Top comments (0)

Feature flag article image

Create a feature flag in your IDE in 5 minutes with LaunchDarkly’s MCP server ⏰

How to create, evaluate, and modify flags from within your IDE or AI client using natural language with LaunchDarkly's new MCP server. Follow along with this tutorial for step by step instructions.

Read full post

👋 Kindness is contagious

Discover fresh viewpoints in this insightful post, supported by our vibrant DEV Community. Every developer’s experience matters—add your thoughts and help us grow together.

A simple “thank you” can uplift the author and spark new discussions—leave yours below!

On DEV, knowledge-sharing connects us and drives innovation. Found this useful? A quick note of appreciation makes a real impact.

Okay