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

Breadth-First Search (BFS) in Graphs

Problem Statement

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores the neighbor nodes level by level. Given a starting node in a graph, BFS visits all its adjacent nodes, then moves on to their neighbors, and so on.

BFS is commonly used for finding the shortest path in unweighted graphs, level order traversal of trees, and in many other scenarios where step-wise discovery is important.

Examples

Input Graph BFS Traversal Description
{0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1], 4: [1]}
[0, 1, 2, 3, 4] Starting from node 0, it visits all directly connected nodes (1 and 2), then expands to 1's neighbors (3 and 4).
{10: [20, 50], 20: [10, 40], 30: [50], 40: [20, 50], 50: [10, 30, 40]}
[10, 20, 50, 40, 30] Starting from node 10, BFS visits 20 and 50 first, then explores 50's neighbors (40 and 30). Cycles are avoided.
{1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3, 5], 5: [4]}
[1, 2, 3, 4, 5] A densely connected graph; BFS explores all layers level-by-level starting from node 1.
{1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}
[1, 2, 3, 4] A linear chain; BFS behaves like DFS here but still visits breadth-first per level.
{0: [1], 1: [0], 2: [3], 3: [2]}
[0, 1] Graph has two disconnected components; BFS from node 0 covers only the first component.

Visualization Player

Solution

Understanding the Problem

Breadth-First Search (BFS) is a fundamental algorithm used to traverse or search nodes in a graph or tree. The core idea is to explore all nodes at the current depth level before moving on to the next level. BFS uses a queue to keep track of the order in which to visit nodes and ensures each node is visited exactly once using a visited set or array.

Let’s say you’re given a graph as an adjacency list, and you need to traverse all its nodes starting from a given source. The problem becomes even more interesting when you have disconnected graphs or cycles.

Our goal is to understand how BFS works step-by-step and handle these special scenarios properly.

Step-by-Step Solution with Example

step 1: Define the Graph

We will represent the graph using an adjacency list. For example:


const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A'],
  D: ['B']
};

step 2: Understand the Starting Point

We start BFS from node 'A'. This means we will visit 'A' first and then its neighbors — 'B' and 'C'.

step 3: Use a Queue and a Visited Set

We use a queue to manage the order of visiting nodes, and a set to keep track of visited nodes to avoid revisiting.


const queue = ['A'];
const visited = new Set(['A']);

step 4: Begin the Traversal

We dequeue 'A', visit its neighbors 'B' and 'C', and add them to the queue and the visited set.


while (queue.length > 0) {
  const current = queue.shift();
  console.log(current); // print visited node

  for (const neighbor of graph[current]) {
    if (!visited.has(neighbor)) {
      queue.push(neighbor);
      visited.add(neighbor);
    }
  }
}

step 5: Track the Order of Visit

In this example, the BFS traversal order will be: A → B → C → D.

step 6: Print or Store the Result

You can print each visited node, or store them in an array for further analysis.

Edge Cases

1. Disconnected Graph

If the graph has multiple disconnected components, starting BFS from one node will only cover its connected component. To visit all nodes, run BFS for each unvisited node:


for (const node in graph) {
  if (!visited.has(node)) {
    bfs(node);
  }
}

2. Graph with Cycles

Cycles can cause infinite loops if visited nodes are not tracked. Always use a visited set to mark nodes that have already been added to the queue.

3. Self-loops

A node may have an edge to itself (e.g., A: ['A']). The visited set will ensure it’s not processed again and again.

4. Empty Graph

If the graph is empty, return an empty traversal list. Always check for this condition before starting BFS.

Finally

BFS is a powerful and intuitive graph traversal algorithm especially useful for problems involving levels, shortest paths in unweighted graphs, or connectivity checks. By thinking of BFS like spreading a message — where each person tells all their immediate friends first — you can intuitively understand how it works. With careful use of a queue and visited tracking, you can avoid pitfalls like cycles or missed components in disconnected graphs.

Always test your implementation against edge cases like cycles, disconnected graphs, and empty inputs to ensure robustness.

Algorithm Steps

  1. Initialize a queue and a visited set.
  2. Enqueue the starting node and mark it as visited.
  3. While the queue is not empty:
    1. Dequeue the front node.
    2. Process or record the node.
    3. For each adjacent node of the current node:
      1. If it is not visited, enqueue it and mark it as visited.
  4. Repeat until the queue is empty.

Code

JavaScript
function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

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

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

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(V + E)Even in the best case, BFS must explore every vertex (V) and every edge (E) to ensure complete traversal of the graph component.
Average CaseO(V + E)On average, BFS visits all vertices and edges once during the traversal.
Worst CaseO(V + E)In the worst case, such as a fully connected graph, BFS still processes all vertices and edges exactly once.

Space Complexity

O(V)

Explanation: The space complexity is proportional to the number of vertices because the queue and visited set each store up to V elements.


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...