Binary TreesBinary Trees36
  1. 1Preorder Traversal of a Binary Tree using Recursion
  2. 2Preorder Traversal of a Binary Tree using Iteration
  3. 3Inorder Traversal of a Binary Tree using Recursion
  4. 4Inorder Traversal of a Binary Tree using Iteration
  5. 5Postorder Traversal of a Binary Tree Using Recursion
  6. 6Postorder Traversal of a Binary Tree using Iteration
  7. 7Level Order Traversal of a Binary Tree using Recursion
  8. 8Level Order Traversal of a Binary Tree using Iteration
  9. 9Reverse Level Order Traversal of a Binary Tree using Iteration
  10. 10Reverse Level Order Traversal of a Binary Tree using Recursion
  11. 11Find Height of a Binary Tree
  12. 12Find Diameter of a Binary Tree
  13. 13Find Mirror of a Binary Tree
  14. 14Left View of a Binary Tree
  15. 15Right View of a Binary Tree
  16. 16Top View of a Binary Tree
  17. 17Bottom View of a Binary Tree
  18. 18Zigzag Traversal of a Binary Tree
  19. 19Check if a Binary Tree is Balanced
  20. 20Diagonal Traversal of a Binary Tree
  21. 21Boundary Traversal of a Binary Tree
  22. 22Construct a Binary Tree from a String with Bracket Representation
  23. 23Convert a Binary Tree into a Doubly Linked List
  24. 24Convert a Binary Tree into a Sum Tree
  25. 25Find Minimum Swaps Required to Convert a Binary Tree into a BST
  26. 26Check if a Binary Tree is a Sum Tree
  27. 27Check if All Leaf Nodes are at the Same Level in a Binary Tree
  28. 28Lowest Common Ancestor (LCA) in a Binary Tree
  29. 29Solve the Tree Isomorphism Problem
  30. 30Check if a Binary Tree Contains Duplicate Subtrees of Size 2 or More
  31. 31Check if Two Binary Trees are Mirror Images
  32. 32Calculate the Sum of Nodes on the Longest Path from Root to Leaf in a Binary Tree
  33. 33Print All Paths in a Binary Tree with a Given Sum
  34. 34Find the Distance Between Two Nodes in a Binary Tree
  35. 35Find the kth Ancestor of a Node in a Binary Tree
  36. 36Find All Duplicate Subtrees in a Binary Tree
GraphsGraphs46
  1. 1Breadth-First Search in Graphs
  2. 2Depth-First Search in Graphs
  3. 3Number of Provinces in an Undirected Graph
  4. 4Connected Components in a Matrix
  5. 5Rotten Oranges Problem - BFS in Matrix
  6. 6Flood Fill Algorithm - Graph Based
  7. 7Detect Cycle in an Undirected Graph using DFS
  8. 8Detect Cycle in an Undirected Graph using BFS
  9. 9Distance of Nearest Cell Having 1 - Grid BFS
  10. 10Surrounded Regions in Matrix using Graph Traversal
  11. 11Number of Enclaves in Grid
  12. 12Word Ladder - Shortest Transformation using Graph
  13. 13Word Ladder II - All Shortest Transformation Sequences
  14. 14Number of Distinct Islands using DFS
  15. 15Check if a Graph is Bipartite using DFS
  16. 16Topological Sort Using DFS
  17. 17Topological Sort using Kahn's Algorithm
  18. 18Cycle Detection in Directed Graph using BFS
  19. 19Course Schedule - Task Ordering with Prerequisites
  20. 20Course Schedule 2 - Task Ordering Using Topological Sort
  21. 21Find Eventual Safe States in a Directed Graph
  22. 22Alien Dictionary Character Order
  23. 23Shortest Path in Undirected Graph with Unit Distance
  24. 24Shortest Path in DAG using Topological Sort
  25. 25Dijkstra's Algorithm Using Set - Shortest Path in Graph
  26. 26Dijkstra’s Algorithm Using Priority Queue
  27. 27Shortest Distance in a Binary Maze using BFS
  28. 28Path With Minimum Effort in Grid using Graphs
  29. 29Cheapest Flights Within K Stops - Graph Problem
  30. 30Number of Ways to Reach Destination in Shortest Time - Graph Problem
  31. 31Minimum Multiplications to Reach End - Graph BFS
  32. 32Bellman-Ford Algorithm for Shortest Paths
  33. 33Floyd Warshall Algorithm for All-Pairs Shortest Path
  34. 34Find the City With the Fewest Reachable Neighbours
  35. 35Minimum Spanning Tree in Graphs
  36. 36Prim's Algorithm for Minimum Spanning Tree
  37. 37Disjoint Set (Union-Find) with Union by Rank and Path Compression
  38. 38Kruskal's Algorithm - Minimum Spanning Tree
  39. 39Minimum Operations to Make Network Connected
  40. 40Most Stones Removed with Same Row or Column
  41. 41Accounts Merge Problem using Disjoint Set Union
  42. 42Number of Islands II - Online Queries using DSU
  43. 43Making a Large Island Using DSU
  44. 44Bridges in Graph using Tarjan's Algorithm
  45. 45Articulation Points in Graphs
  46. 46Strongly Connected Components using Kosaraju's Algorithm

Depth-First Search (DFS) in Graphs

Problem Statement

Depth-First Search (DFS) is a popular graph traversal technique that explores as far along a branch as possible before backtracking. Starting from a node, DFS goes deep into the graph, exploring child nodes before sibling nodes.

DFS is useful for tasks like detecting cycles, pathfinding, topological sorting, and solving puzzles with backtracking.

Examples

Input Graph (Adjacency List) DFS Output Description
{1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}
1 → 2 → 4 → 5 → 3 Classic DFS tree with backtracking: visits 2 → 4 → 5, then backtracks to visit 3.
{1: [2, 3], 2: [1, 4], 3: [1, 5], 4: [2], 5: [3, 6], 6: [5]}
1 → 2 → 4 → 3 → 5 → 6 DFS explores left from 1 to 2 → 4, backtracks to 3 → 5 → 6. Deep tree with branching.
{1: [2, 3], 2: [1, 3, 4], 3: [1, 2], 4: [2, 5], 5: [4]}
1 → 2 → 3 → 4 → 5 Cycle between 1-2-3 handled properly; DFS continues deeper through node 4 to 5.
{1: [2], 2: [1, 3, 4], 3: [2], 4: [2, 5, 6], 5: [4], 6: [4]}
1 → 2 → 3 → 4 → 5 → 6 DFS covers a “Y”-shaped graph with multiple forks under node 4.
{0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3]}
0 → 1 → 2 → 3 → 4 Linear path graph; DFS proceeds from left to right in straight line without backtracking.

Visualization Player

Solution

Understanding the Problem

We are given a graph with a set of nodes and edges. The task is to traverse the graph using the Depth-First Search (DFS) algorithm. DFS explores as far as possible along each branch before backtracking, ensuring that each node is visited once.

This traversal technique is foundational for many graph problems like counting connected components, detecting cycles, and solving maze-like puzzles. In this lesson, we will understand how DFS works step-by-step and apply it to a practical example with beginner-friendly explanations.

Step-by-Step Solution with Example

Step 1: Define the Graph

Let's take a sample undirected graph represented as an adjacency list:

{
  0: [1, 2],
  1: [0, 3],
  2: [0],
  3: [1, 4],
  4: [3]
}

This graph has 5 nodes. The connections (edges) between nodes are undirected, meaning you can go both ways along the edge. For example, 0 is connected to 1 and 2, and 1 is connected back to 0 and to 3.

Step 2: Understand the DFS Approach

DFS starts at a node (say, node 0), marks it as visited, and then recursively explores each unvisited neighbor. Once all neighbors are visited, it backtracks.

We use a visited array or set to keep track of nodes we have already seen, to avoid visiting the same node again and getting stuck in cycles.

Step 3: Implement the DFS Logic

Here’s a basic recursive DFS implementation:

function dfs(node, visited, graph) {
  visited[node] = true;
  console.log("Visited", node);
  for (let neighbor of graph[node]) {
    if (!visited[neighbor]) {
      dfs(neighbor, visited, graph);
    }
  }
}

Step 4: Apply DFS to the Graph

We start from node 0 and visit its neighbors one by one. Here's how it works:

  1. Visit node 0 ➝ mark as visited
  2. From 0, go to node 1 ➝ mark 1 visited
  3. From 1, go to node 3 ➝ mark 3 visited
  4. From 3, go to node 4 ➝ mark 4 visited
  5. Backtrack to 3 ➝ 1 ➝ 0
  6. From 0, go to node 2 ➝ mark 2 visited

All nodes are now visited.

Step 5: Visualize the Order

The order of traversal will be: 0 → 1 → 3 → 4 → 2

Edge Cases

Disconnected Graph

If the graph is disconnected (e.g., two separate subgraphs), starting DFS from one node will not visit all nodes. In such cases, we run DFS for every unvisited node in a loop:

for (let node in graph) {
  if (!visited[node]) {
    dfs(node, visited, graph);
  }
}

Graph with Cycles

If a graph contains cycles, DFS can fall into infinite loops without a visited check. That’s why we always verify whether a node has already been visited before calling DFS on it.

Directed Graphs

DFS logic remains the same, but it follows the direction of edges. That means if there's an edge from A → B, DFS can go from A to B, but not from B to A unless a separate edge exists.

Empty Graph

If the graph has no nodes or edges, the DFS simply ends immediately with no output. Always validate inputs before running DFS logic.

Finally

Depth-First Search is a powerful tool to explore and analyze graphs. Understanding the traversal order and marking visited nodes are the key steps to avoid infinite loops and ensure correctness. For disconnected graphs or graphs with cycles, we slightly extend the basic DFS to handle all components safely.

As you practice, try applying DFS to real-world scenarios like social networks (friend groups), map navigation (paths and roads), and puzzle solving (mazes). This will strengthen your intuition and mastery over graph traversal techniques.

Algorithm Steps

  1. Initialize a visited set.
  2. Start DFS from the given node.
  3. Mark the current node as visited and process it.
  4. Recursively (or using a stack) visit all unvisited neighbors.
  5. Repeat until all connected nodes have been visited.

Code

JavaScript
function dfs(graph, start, visited = new Set(), result = []) {
  if (visited.has(start)) return;
  visited.add(start);
  result.push(start);

  for (const neighbor of graph[start] || []) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, result);
    }
  }
  return result;
}

const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0],
  3: [1]
};

console.log("DFS from node 0:", dfs(graph, 0)); // Output: [0, 1, 3, 2]

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(V + E)DFS visits each node and edge once, even in the best case where traversal may end early due to no unvisited neighbors.
Average CaseO(V + E)Each node is explored once and each edge is checked once, regardless of the structure of the graph.
Worst CaseO(V + E)In the worst case, DFS explores all vertices and all edges, particularly in a densely connected graph.

Space Complexity

O(V)

Explanation: The space used is proportional to the number of vertices due to the visited set and the recursion stack or explicit stack used in the process.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.


Loading comments...