DFS in Data Structure: Depth-First Search Algorithm Explained

How Does DFS Work?

Depth-first search explores the edges that come out of the most recently discovered vertex; let’s call it s. The algorithm traverses these edges to visit the unexplored vertices. When all of the s’s (the discovered vertex's) edges are explored, the search backtracks until it reaches an unexplored vertex.

This process continues until all vertices that are reachable from the original source vertex are visited and discovered. If there are any unvisited vertices, the algorithm selects one of them as a new source and repeats the search from that vertex. The algorithm continues until all vertices are discovered.

The key thing to consider is ensuring that every vertex is visited once. Also, DFS uses a stack data structure (either explicitly or via recursion) to keep track of the vertices to visit next.

Steps of DFS Algorithm

Here are the detailed DFS algorithm steps that outline the implementation of DFS traversal:

• Step 1: Create an empty stack and a list to keep track of visited nodes.
• Step 2: Select any vertex to start the traversal. Push that vertex onto the stack and mark it as visited.
• Step 3: While the stack is not empty:
      - Look at the top node in the stack.
      - If it has any unvisited neighbors:
          • Pick one, push it onto the stack, and mark it as visited.
      - If no unvisited neighbors remain, remove (pop) the node from the stack and backtrack.
• Step 4: Repeat this process until all reachable nodes are visited and the stack is empty.

Complexity of DFS Algorithm

The amount of time an algorithm takes in relation to the amount of input it gets is referred to as its time complexity. A function called space complexity indicates how much memory (space) an algorithm needs in relation to the amount of input it receives. Let’s examine the time and space complexities for DFS implementation in programming:

1. Time Complexity of DFS

The time complexity of Depth-First Search (DFS) is:

• O(V + E)
  Where:
  • V = Number of vertices (nodes)
  • E = Number of edges

Explanation:

• DFS visits each vertex exactly once.
• Each vertex explores all its adjacent edges exactly once.
• Hence, the overall time complexity becomes proportional to the total number of vertices (V) plus the total number of edges (E).

This complexity applies to standard graph representations such as adjacency lists. If an adjacency matrix is used, the complexity becomes O(V²), as DFS must scan an entire row (or column) for each vertex.

2. Space Complexity of DFS

The space complexity of Depth First Search (DFS) varies based on the structure of the graph or tree being traversed. Below are the main considerations:

• General Case: 

The space complexity of Depth-First Search (DFS) is:

• O(V) 

Where: V = Number of vertices (nodes)

This is because, in the worst case, the recursion stack (for recursive DFS) or the explicit stack (in iterative DFS) can grow up to the number of vertices, particularly in linear chain-like structures.

• Tree Structure:

For trees, the space complexity is typically described as O(h), where h is the height of the tree. Since DFS dives deep along each branch before backtracking, the maximum depth of the recursion or explicit stack corresponds to the height of the tree.

• Special Case:

In certain scenarios, especially when dealing with search trees that have a defined branching factor, the space complexity may be noted as O(bm), where b is the branching factor, and m is the maximum depth of the search tree. However, this notation is more common in specialized contexts like AI search algorithms rather than standard graph or tree traversals.

For typical graph or tree traversal, the most widely cited space complexity for DFS is O(V).

Struggling with data structures? Let upGrad's Data Structures Courses simplify complex concepts for you.

Different Approaches to Implement DFS Algorithm

Each graph vertex is assigned to one of two groups in a typical DFS implementation:

• Not Visited
• Visited
• In some implementations, a third state (Being Visited) tracks nodes currently in the recursion or stack, helping detect cycles.

The Depth-First Search algorithm's goal is to explore all reachable nodes while avoiding cycles. DFS can be implemented in two main ways: Recursive Approach and Iterative Approach

The iterative DFS method uses an explicit stack instead of recursion. The algorithm pushes the starting node onto the stack and explores nodes by popping them off the stack and adding their unvisited neighbors. This process continues until the stack is empty. Compared to the recursive method, the iterative method provides better memory control and avoids deep recursion issues.

1. Recursive Approach

The recursive method uses function calls. For every unvisited neighbor, the DFS algorithm recursively calls itself. This process is similar to navigating a maze: you take one route until you reach a dead end, then backtrack and try a different route.

The DFS algorithm tracks visited nodes to prevent infinite loops. While this method is simple and intuitive, it may consume more memory in deep graphs due to recursive function calls.

The recursive DFS in data structure works as follows:

1. Start at the given node.
2. Mark it as visited.
3. Recursively call DFS for each unvisited neighbor.
4. Backtrack when no unvisited neighbors remain.
5. Continue until all reachable nodes are visited.

This recursive DFS in the data structure tracks nodes through the call stack. When there are no unvisited neighbors, the recursion ends.

Example

Assume A, B, C, and D are nodes in a graph. You start with node A:

• Start at A and mark it as visited.
• Move to an unvisited neighbor, B, and mark it as visited.
• Proceed to another unvisited neighbor of B, C, and mark it as visited.
• If C has no unvisited neighbors, backtrack to B, then to A.
• Finally, visit any remaining unvisited nodes, such as D.

This procedure ensures that every path is explored before backtracking.

Code for implementing DFS using recursion: 

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []
def add_edge(parent, child):
    parent.children.append(child)
def recursive_dfs(node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node.value, end=" ")  # Process the node
    for child in node.children:
        if child not in visited:
            recursive_dfs(child, visited)
# Example usage
if __name__ == "__main__":
    # Create nodes
    A = Node('A')
    B = Node('B')
    C = Node('C')
    D = Node('D')
    E = Node('E')
    # Add edges
    add_edge(A, B)
    add_edge(A, C)
    add_edge(B, D)
    add_edge(C, E)
    print("Recursive DFS Traversal:")
    recursive_dfs(A)

The algorithm can be modified to keep track of the edges instead of vertices because each edge describes the nodes at each end. This strategy is useful when you are attempting to reconstruct the traversed tree after processing each node. 

In the case of a forest or group of trees, the algorithm can be expanded to include an outer loop that iterates over all the trees in order to process every single node.  

2. Iterative Approach

The iterative Depth-First Search (DFS) method uses a stack data structure. The process of this stack-based DFS approach is as follows:

1. Push the starting node onto the stack.
2. While the stack is not empty:
   1. Pop a node from the stack.
   2. If the node has not been visited, mark it as visited.
   3. Push all unvisited neighbors onto the stack.
3. Repeat until all reachable nodes are visited.

By using an explicit stack, this method eliminates the overhead associated with recursive calls.

Example

Consider a graph with nodes A, B, C, and D:

• Push A onto the stack.
• Pop A, mark it as visited, and push its unvisited neighbors (B).
• Pop B, mark it as visited, and push its unvisited neighbors (C).
• Continue this process until all nodes have been visited.

The stack simplifies managing which nodes to visit next.

Python code for iterative DFS: 

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []
def add_edge(parent, child):
    parent.children.append(child)
def iterative_dfs(node):
    visited = set()
    stack = [node]
    while stack:
        current_node = stack.pop()
        if current_node not in visited:
            visited.add(current_node)
            print(current_node.value, end=" ")  # Process the node
            # Add neighbors to the stack in reverse order
            for child in reversed(current_node.children):
                if child not in visited:
                    stack.append(child)
# DFS traversal example
if __name__ == "__main__":
    # Create nodes
    A = Node('A')
    B = Node('B')
    C = Node('C')
    D = Node('D')
    E = Node('E')
    # Add edges
    add_edge(A, B)
    add_edge(A, C)
    add_edge(B, D)
    add_edge(C, E)
    print("\nIterative DFS Traversal:")
    iterative_dfs(A)

The iterative approach avoids recursion depth limits by manually handling the stack. This is useful for large trees or deep structures.  

Both iterative and recursive approaches achieve the same objective by using Depth-First Search (DFS) to explore all paths in a graph. Each method has its benefits. While the recursive method is simpler, it may require more memory in deep graphs. In contrast, the iterative approach provides better control over memory usage, particularly for balanced graphs.

Want to strengthen your DSA skills? Start learning with upGrad's Data Structures and Algorithms (DSA) tutorial today!

DFS Traversal Process

DFS can be better understood through visualization, which illustrates how the algorithm traverses nodes hierarchically. By visually mapping DFS, it becomes clear how the algorithm prioritizes depth over breadth, exploring one path completely before backtracking.

DFS Tree Traversal

The Depth-First Search (DFS) algorithm starts at the root node and explores one branch as deeply as possible before backtracking to visit other branches. DFS-based tree traversal can be performed in three standard ways, depending on the order of visiting the root, left subtree, and right subtree:

1. Preorder Traversal (Root → Left → Right)

Visits the current node first, then recursively traverses the left subtree, followed by the right subtree.

Traversal Order: A → B → C → D → E

2. Inorder Traversal (Left → Root → Right)

Recursively visits all nodes in the left subtree first, processes the current node next, and finally traverses all nodes in the right subtree.

Traversal Order: B → A → D → C → E

3. Postorder Traversal (Left → Right → Root)

Recursively visits all nodes in the left subtree first, then all nodes in the right subtree, and finally processes the current node last.

Traversal Order: B → D → E → C → A

DFS ensures that each branch of a tree is fully explored before moving to another branch.

If you want to learn about inorder, preorder, and postorder traversal, Refer to upGrad’s Understanding Tree Traversal in Data Structures tutorial.

DFS Traversal on Graphs

Unlike trees, graphs can contain cycles and multiple connected components, making DFS traversal more complex. Here’s an example of DFS on a directed graph, starting from node A:

Step-by-Step DFS Traversal:

Final DFS Traversal Order: A → B → D → C → E

Key Observations from the DFS Example:

• DFS explores as deeply as possible before backtracking to explore other paths.
• A stack (explicit or recursive) ensures nodes are visited only when necessary.
• DFS guarantees all reachable nodes are visited but does not always find the shortest path (unlike BFS).
• For cyclic graphs, a "visited" list is necessary to prevent infinite loops.

Example Code:
def iterative_dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=" → ")
            visited.add(node)
            # Push neighbors in reverse order for preorder traversal
            for neighbor in reversed(graph[node]):
                stack.append(neighbor)
# Example graph
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}

iterative_dfs(graph, 'A')  # Output: A → B → D → C → E → 

Want to improve your problem-solving skills? Start with the DFS (Depth First Traversal) in Data Structure blog and learn how DFS works.

Common Mistakes and How to Avoid Them?

While DFS is a powerful technique for traversing graphs and trees, it can lead to inefficiencies or incorrect results if certain challenges are not addressed. Recognizing and resolving these common mistakes is crucial for effective DFS implementation.

1. Infinite Loops in DFS

One of the most common mistakes when implementing DFS is failing to track visited nodes. Without proper tracking, the algorithm may revisit the same nodes repeatedly, leading to an infinite loop. This issue arises when DFS explores cyclic graphs without maintaining a record of previously visited nodes, causing excessive resource consumption and potential program crashes.

Solution:

• Use a "visited" set or list to track explored nodes.
• Mark nodes as visited immediately upon exploration to prevent unnecessary revisits.
• For cyclic graphs, implement cycle detection techniques to ensure DFS terminates correctly.

If not handled properly, infinite loops can render DFS ineffective for cyclic graphs, making it impossible to obtain meaningful results.

2. Forgetting to Mark Nodes

Another frequent error is failing to mark nodes as visited after processing them. If nodes are not labeled correctly, DFS may revisit them unnecessarily, leading to:

• Redundant computations
• Increased execution time
• Wasted memory and processing resources

This mistake is especially problematic in large-scale graphs, where inefficient traversal can significantly impact performance.

Solution:

• Use explicit data structures (e.g., boolean arrays, hash sets) to mark nodes.
• Modify node properties or adjacency lists, if applicable, to indicate visited status.
• Ensure each node is processed only once to improve efficiency.

Want to improve your coding efficiency? Explore upGrad's Data Structures & Algorithms course and sharpen your skills.

Applications of DFS in Data Structure

Developers primarily select a DFS in order to enable access to the same data from several places. For instance, a team that is separated over the globe must be able to access the same files in order to work together. DFS can be used in network analysis to help identify connectivity, detect deadlocks, and analyze network structures for routing and security. Let’s understand the use cases of DFS: 

1. Detecting Cycles in Graphs

The DFS technique is used to identify cycles in a directed graph. This is an essential task in applications such as dependency resolution and deadlock detection in operating systems. DFS produces a DFS tree (or a DFS forest in disconnected graphs), representing the graph’s vertices and edges.

When executing DFS on a disconnected graph, multiple trees are formed; thus, we use the term DFS Forest to refer to all of them. Each of these trees contains specific types of edges:

• Tree Edge 
• Forward Edge 
• Cross Edge 
• Back Edge

To identify a cycle in a directed graph, we focus solely on the Back Edge, which connects a vertex to one of its ancestors in the DFS tree.

Also Read: Top 30+ DSA projects with source code in 2025

2. Finding Connected Components

A directed graph is termed strongly connected if a path exists from every vertex to all other vertices. Strongly Connected Components (SCCs) represent a key concept in graph theory and algorithms. A Strongly Connected Component in a directed graph is a subset of vertices where each vertex can be reached from any other vertex within the same subset through directed edges.

Identifying SCCs can provide insights into a graph’s structure and connectivity, with applications in social network analysis, web crawling, and network routing. Kosaraju’s Algorithm, Tarjan’s Algorithm, and the DFS-based Condensation Graph approach are common methods for finding SCCs.

3. Topological Sorting

Topological Sorting is primarily used for scheduling tasks based on dependencies. In computer science, applications include instruction scheduling, determining formula cell evaluation sequences in spreadsheets, logic synthesis, arranging compilation tasks in makefiles, data serialization, and resolving symbol dependencies in linkers.

Topological sorting is only applicable to Directed Acyclic Graphs (DAGs). In DFS, a vertex is added to a stack after visiting all its descendants. The order in which vertices are popped from the stack gives the correct topological order.

4. Pathfinding in Mazes and Games

Mazes offer a traditional challenge. These situations highlight the strengths of Depth-First Search. DFS explores all potential paths to locate an exit. However, DFS does not guarantee the shortest path; Breadth-First Search (BFS) is generally more efficient for this purpose.

In video games, characters frequently navigate intricate settings. Developers use DFS to help characters explore dungeons or mazes. For example, a game might have a maze with multiple exits, and DFS examines each route until it finds a solution.

DFS is also used in robotics to map unknown environments. Robots equipped with sensors use DFS to explore new areas. However, real-world implementations often combine DFS with other techniques, such as A or Dijkstra’s Algorithm, for better efficiency.

5. Solving Puzzle Problems

Puzzles often require examining different possibilities. Depth-first search (DFS) is useful for solving Sudoku, jigsaws, and pathfinding challenges. By exploring every possible move, DFS ensures that all solutions are considered.

Many puzzle games use DFS. For example, in a game where the objective is to connect dots while avoiding crossing lines, DFS explores each connection possibility.

In strategy games like chess, DFS is used in the Minimax Algorithm to evaluate possible moves and outcomes, helping players strategize. DFS alone does not guarantee optimal solutions but is effective for exhaustive searches.

DFS is widely used in these situations. Because it can explore all routes, it remains a popular choice among engineers and developers.

Advantages and Disadvantages of DFS

Depth-first search is an efficient algorithm capable of systematically traversing graphs and trees. While it is highly effective in various applications, it does have some limitations. Understanding its advantages and disadvantages helps determine when to use it.

Advantages of DFS

DFS offers advantages such as deep exploration and reduced memory consumption. Key benefits include:

1. Efficient for Deep Traversal Problems

DFS in data structure provides an efficient solution for exploring trees and different types of graphs in data structures. It is particularly useful in scenarios where the solution lies deep within the search space, such as maze solving, pathfinding in Artificial Intelligence, and interpreting nested data structures. 

Since DFS explores an entire branch before moving to the next, it can quickly reach deeply located nodes when necessary. However, this is only efficient if the target node is deep in the structure; otherwise, other search strategies (e.g., BFS) may be better suited.

2. Requires Minimal Memory Compared to BFS

A primary advantage of DFS is its lower memory usage compared to Breadth-First Search (BFS). BFS tracks all nodes at the current level before proceeding, which can require significant memory in wide graphs. In contrast, DFS only maintains nodes on the current traversal path.

DFS has a space complexity of O(V) in the worst case (where V is the number of vertices in the graph). Both recursive and iterative DFS implementations rely on either the system’s call stack (recursion) or an explicit stack (iteration). This feature makes DFS a preferred choice for working with large graphs in memory-constrained environments.

3. Useful for Detecting Connected Components

DFS in data structure is particularly valuable for identifying connected components in undirected graphs. This has numerous applications, including social network analysis (finding communities), cluster detection, image segmentation. DFS ensures all nodes in a connected component are visited efficiently by backtracking when necessary.

Disadvantages of DFS

While DFS offers several advantages, it has limitations that make it unsuitable for certain problems. These drawbacks include:

1. Can Get Stuck in Infinite Loops

DFS can run indefinitely if proper cycle detection is not in place, particularly in graphs with cycles. If the algorithm revisits nodes without tracking visited nodes, it may traverse the same paths repeatedly, leading to infinite loops.

This issue is common in scenarios involving cyclic connections, such as: web crawling and network routing in the Internet of Things. To prevent this, it’s important to maintain a visited set or boolean array to track processed nodes. Without such safeguards, DFS may continuously follow cyclic paths, resulting in non-termination and high computational resource usage.

2. A Weighted Graph Might Not Always Show the Shortest Path

DFS does not always find the shortest path, even in unweighted graphs, since it explores one path to its full depth before backtracking.

In weighted graphs, DFS is unsuitable for shortest-path problems because it does not consider edge weights. Breadth-First Search (BFS) (guarantees shortest paths in unweighted graphs), Dijkstra’s Algorithm (finds the shortest path in weighted graphs), and A Search* (optimized pathfinding with heuristics) are better-suited algorithms for such cases. 

3. Recursive Approach Can Lead to Stack Overflow:

The recursive implementation of DFS in data structure can cause stack overflow errors when working with large graphs or deep recursion. Each recursive function call adds to the system’s call stack, which can grow significantly in graphs with high-depth and deeply nested structures

The recursion depth can reach O(V) in the worst case, where V is the number of vertices, potentially leading to excessive memory usage and program crashes in constrained environments. 

To avoid stack overflow, the iterative DFS approach is often preferred. It uses an explicit stack, which provides better control over memory usage while achieving the same traversal results.

Preparing for coding interviews? Master key concepts with upGrad's Data Structures in Java Tutorial.

Comparing DFS vs BFS: When to Use Them? (Breadth First Search)

BFS and DFS algorithms are widely used in data structures to explore graphs and trees. BFS starts at the top node of a graph and explores all its neighboring nodes level by level until it reaches the root or target node. On the other hand, DFS begins at the top node and follows one path to its end before backtracking to explore other paths.

Key Differences Between DFS and BFS

The fundamental differences between Depth-First Search and Breadth-First Search are summarized in the table below.

When to Use DFS vs BFS?

The choice between DFS vs BFS comparison depends on the specific problem, the nature of the graph or tree, and the traversal requirements. Both algorithms are fundamental tools for exploring graph structures, but their effectiveness varies based on the scenario, such as pathfinding, searching, or resource limitations.

The table below outlines general guidelines for selecting between BFS and DFS algorithms in data structures:

However, we are able to draw some broad conclusions.

• BFS is effective when the solution is closer to the starting node or when dealing with wide graphs.
• DFS is suitable for deep graphs or when the solution is farther from the starting point.
• If a problem involves multiple starting points that need simultaneous exploration, BFS is preferable because it processes nodes level by level.
• BFS is ideal for finding the shortest path in unweighted graphs, while DFS is often used for general pathfinding and backtracking problems.

This comprehensive comparison compares data structure certifications and courses offered by top educational institutions.

How upGrad Helps You Master Data Structures?

Here's how upGrad gives you the tools you need to master data structures and grow in your computer profession.

• Professional Mentoring: Receive exact, individualized comments for clarity and confidence, as well as mentor support that is available around the clock.
• All-encompassing Learning: upGrad combines theoretical ideas with real-world projects to guarantee that data structures, such as DFS, Trees, and Graphs, are properly understood.
• Career Support: upGrad stood out from other sites thanks to its resume-building, mock interview, and job placement services.

Flexible & Engaging: upGrad offers learning in various interesting ways, including live sessions, recorded content, and real-world projects.

Conclusion

DFS in data structures is a fundamental concept. It is essential for anyone looking to deepen their understanding of algorithmic strategies. Gaining proficiency in DFS can help you build and develop more comprehensive problem-solving skills across a variety of challenging scenarios. Examining DFS will give you important insights into effective data traversal techniques, whether you're a professional looking to hone your skills or a student trying to understand the fundamentals.

In addition to developing your technical skill set, studying this subject thoroughly can help you see computer science applications from a broader viewpoint. 

Ready to dive deeper into DFS and other essential algorithms? Explore upGrad's comprehensive online software development courses today. Enroll right away to start your journey for the future! Contact our expert counselors to explore your options!

You can also check these courses:

• Online Artificial Intelligence & Machine Learning Programs
• Explore Cutting-Edge Tech Course

Boost your career with our popular Software Engineering courses, offering hands-on training and expert guidance to turn you into a skilled software developer.

Explore our Popular Software Engineering Courses

Master in-demand Software Development skills like coding, system design, DevOps, and agile methodologies to excel in today’s competitive tech industry.

In-Demand Software Development Skills

Stay informed with our widely-read Software Development articles, covering everything from coding techniques to the latest advancements in software engineering.

Read our Popular Articles related to Software