DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Queue in BFS

Why BFS Uses a Queue

Breadth-first search explores a graph level by level — all nodes at distance 1 from the source before distance 2, all at distance 2 before distance 3, and so on. The FIFO property of a queue is what enforces this order.

BFS on a graph from source S:

       S
      / \
     A   B       Distance 1 — processed AFTER S, BEFORE C,D,E,F
    / \   \
   C   D   E     Distance 2 — processed AFTER A,B, BEFORE G
  /
 G               Distance 3

Queue state during BFS:
  Start:    [S]
  Process S: enqueue A, B → [A, B]
  Process A: enqueue C, D → [B, C, D]
  Process B: enqueue E    → [C, D, E]
  Process C: enqueue G    → [D, E, G]
  Process D: (no children) → [E, G]
  Process E: (no children) → [G]
  Process G: (no children) → []

FIFO ensures A and B are both processed before C, D, E —
level-by-level exploration. A stack would dive deep immediately.

BFS Template

Every BFS problem follows the same structural template. Variations only change what is stored in the queue and what computation happens at each node.

BFS Template:

  visited = set()
  queue   = deque([start])
  visited.add(start)
  dist[start] = 0

  while queue:
      node = queue.popleft()         ← DEQUEUE (process node)

      for neighbour in graph[node]:
          if neighbour not in visited:
              visited.add(neighbour)  ← MARK ON ENQUEUE (not dequeue)
              dist[neighbour] = dist[node] + 1
              queue.append(neighbour) ← ENQUEUE

Critical rule: mark visited WHEN ENQUEUING, not when dequeuing.
  Marking on dequeue allows the same node to be enqueued multiple
  times from different neighbours, causing O(E) redundant processing
  and potentially wrong distance values.

Application 1: Level-Order Tree Traversal

Problem: Print all nodes of a binary tree level by level.

Key technique: Before processing each level, record levelSize = queue.size(). Dequeue exactly levelSize nodes — all belong to the current level. Their children form the next level.

Java

Try it out

import java.util.*;

public class LevelOrderTraversal {

    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    // Returns list of levels — each inner list is one level
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();          // Number of nodes at this level
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);

                if (node.left  != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(level);
        }

        return result;
    }

    // Variant: right side view — last element of each level
    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (i == levelSize - 1) result.add(node.val); // Last = rightmost

                if (node.left  != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        //        3
        //       / \
        //      9  20
        //        /  \
        //       15   7
        TreeNode root = new TreeNode(3);
        root.left  = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left  = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(levelOrder(root));      // [[3], [9, 20], [15, 7]]
        System.out.println(rightSideView(root));   // [3, 20, 7]
    }
}

Output:
[[3], [9, 20], [15, 7]]
[3, 20, 7]

Dry Run: Level-Order on the Tree Above

Tree:       3
           / \
          9  20
            /  \
           15   7

queue=[3], result=[]

Level 1: levelSize=1
  dequeue 3 → level=[3] → enqueue 9, 20
  result=[[3]], queue=[9,20]

Level 2: levelSize=2
  dequeue 9  → level=[9]  → no children
  dequeue 20 → level=[9,20] → enqueue 15, 7
  result=[[3],[9,20]], queue=[15,7]

Level 3: levelSize=2
  dequeue 15 → level=[15] → no children
  dequeue 7  → level=[15,7] → no children
  result=[[3],[9,20],[15,7]], queue=[]

The key: process exactly levelSize nodes per iteration.
Children enqueued during one level-loop belong to the NEXT level.

Application 2: Shortest Path in Unweighted Graph

Problem: Find the shortest path (minimum number of edges) from source to target.

Java

Try it out

import java.util.*;

public class ShortestPathBFS {

    public static int shortestPath(Map<Integer, List<Integer>> graph,
                                   int source, int target) {
        if (source == target) return 0;

        Queue<Integer>       queue   = new ArrayDeque<>();
        Map<Integer, Integer> dist   = new HashMap<>();

        queue.offer(source);
        dist.put(source, 0);

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int neighbour : graph.getOrDefault(node, Collections.emptyList())) {
                if (!dist.containsKey(neighbour)) {
                    dist.put(neighbour, dist.get(node) + 1);

                    if (neighbour == target) return dist.get(neighbour);

                    queue.offer(neighbour);
                }
            }
        }

        return -1;   // Target not reachable
    }

    // Also return the actual path
    public static List<Integer> shortestPathNodes(
            Map<Integer, List<Integer>> graph, int source, int target) {

        Queue<Integer>       queue  = new ArrayDeque<>();
        Map<Integer,Integer> parent = new HashMap<>();

        queue.offer(source);
        parent.put(source, -1);   // Source has no parent

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (node == target) break;

            for (int nb : graph.getOrDefault(node, Collections.emptyList())) {
                if (!parent.containsKey(nb)) {
                    parent.put(nb, node);
                    queue.offer(nb);
                }
            }
        }

        if (!parent.containsKey(target)) return Collections.emptyList();

        // Reconstruct path from target back to source
        List<Integer> path = new ArrayList<>();
        for (int curr = target; curr != -1; curr = parent.get(curr)) {
            path.add(0, curr);
        }
        return path;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        g.put(0, Arrays.asList(1, 2));
        g.put(1, Arrays.asList(0, 3, 4));
        g.put(2, Arrays.asList(0, 4));
        g.put(3, Arrays.asList(1, 5));
        g.put(4, Arrays.asList(1, 2, 5));
        g.put(5, Arrays.asList(3, 4));

        System.out.println(shortestPath(g, 0, 5));          // 3
        System.out.println(shortestPathNodes(g, 0, 5));     // [0, 1, 4, 5] or similar
    }
}

Output:
3
[0, 1, 4, 5]

Application 3: Rotting Oranges — Multi-Source BFS

Problem: A grid has fresh oranges (1), rotten oranges (2), and empty cells (0). Every minute, each rotten orange infects adjacent fresh ones. Return the minimum minutes until no fresh oranges remain, or -1 if impossible.

Multi-source BFS: All rotten oranges start simultaneously at minute 0. BFS fans out from all sources at once — each fresh orange is reached at the time of the nearest rotten orange.

Java

Try it out

import java.util.*;

public class RottingOranges {

    public static int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        int fresh = 0;

        // Step 1: Find all initially rotten oranges (sources) and count fresh
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) queue.offer(new int[]{r, c, 0}); // {row, col, time}
                else if (grid[r][c] == 1) fresh++;
            }
        }

        if (fresh == 0) return 0;   // No fresh oranges

        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        int maxTime  = 0;

        // Step 2: Multi-source BFS
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], time = curr[2];

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;   // Mark rotten
                    fresh--;
                    maxTime = Math.max(maxTime, time + 1);
                    queue.offer(new int[]{nr, nc, time + 1});
                }
            }
        }

        return fresh == 0 ? maxTime : -1;   // -1 if fresh oranges remain
    }

    public static void main(String[] args) {
        int[][] g1 = {{2,1,1},{1,1,0},{0,1,1}};
        int[][] g2 = {{2,1,1},{0,1,1},{1,0,1}};
        int[][] g3 = {{0,2}};

        System.out.println(orangesRotting(g1));  // 4
        System.out.println(orangesRotting(g2));  // -1 (bottom-left isolated)
        System.out.println(orangesRotting(g3));  // 0 (no fresh oranges)
    }
}

Output:
4
-1
0

Dry Run: `[[2,1,1],[1,1,0],[0,1,1]]`

Grid:           Initial rotten: (0,0)   Fresh: 6
  2 1 1
  1 1 0
  0 1 1

queue=[(0,0,t=0)], fresh=6

Process (0,0,0): infect (0,1)→t=1, (1,0)→t=1
  grid: 2 2 1        queue=[(0,1,1),(1,0,1)], fresh=4
        2 1 0
        0 1 1

Process (0,1,1): infect (0,2)→t=2, (1,1)→t=2
  grid: 2 2 2        queue=[(1,0,1),(0,2,2),(1,1,2)], fresh=2
        2 2 0
        0 1 1

Process (1,0,1): no fresh neighbours (all adjacent are 0 or already rotten)

Process (0,2,2): no fresh neighbours

Process (1,1,2): infect (2,1)→t=3
  grid: 2 2 2        queue=[(2,1,3)], fresh=1
        2 2 0
        0 2 1

Process (2,1,3): infect (2,2)→t=4
  grid: 2 2 2        queue=[(2,2,4)], fresh=0
        2 2 0
        0 2 2

Process (2,2,4): no fresh neighbours

fresh=0, maxTime=4 → return 4 ✓

Application 4: 01 Matrix — Distance to Nearest 0

Problem: Given a binary matrix, find the distance to the nearest 0 for every cell.

Multi-source BFS approach: Treat ALL 0-cells as sources at distance 0. BFS simultaneously from all of them — each 1-cell is reached at the distance of its nearest 0.

Java

Try it out

import java.util.*;

public class ZeroOneMatrix {

    public static int[][] updateMatrix(int[][] mat) {
        int rows = mat.length, cols = mat[0].length;
        int[][] dist  = new int[rows][cols];
        Queue<int[]> q = new ArrayDeque<>();

        // Seed all 0-cells at distance 0; mark 1-cells as unvisited (MAX_VALUE)
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (mat[r][c] == 0) {
                    dist[r][c] = 0;
                    q.offer(new int[]{r, c});
                } else {
                    dist[r][c] = Integer.MAX_VALUE;
                }
            }
        }

        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

        // Multi-source BFS
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1];

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && dist[nr][nc] > dist[r][c] + 1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    q.offer(new int[]{nr, nc});
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int[][] m1 = {{0,0,0},{0,1,0},{0,0,0}};
        int[][] m2 = {{0,0,0},{0,1,0},{1,1,1}};

        int[][] r1 = updateMatrix(m1);
        for (int[] row : r1) System.out.println(Arrays.toString(row));
        // [0,0,0]  [0,1,0]  [0,0,0]

        System.out.println("---");
        int[][] r2 = updateMatrix(m2);
        for (int[] row : r2) System.out.println(Arrays.toString(row));
        // [0,0,0]  [0,1,0]  [1,2,1]
    }
}

Output:
[0, 0, 0]
[0, 1, 0]
[1, 2, 1]

Application 5: Word Ladder

Problem: Given a beginWord, endWord, and a word list, find the length of the shortest transformation sequence from beginWord to endWord where each step changes exactly one character and every intermediate word must be in the word list.

BFS insight: Each word is a node; two words are connected if they differ by exactly one character. BFS finds the shortest path — fewest word transformations.

Java

Try it out

import java.util.*;

public class WordLadder {

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String>   wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;

        Queue<String> queue   = new ArrayDeque<>();
        Set<String>   visited = new HashSet<>();

        queue.offer(beginWord);
        visited.add(beginWord);
        int steps = 1;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            steps++;

            for (int i = 0; i < levelSize; i++) {
                String word = queue.poll();
                char[] chars = word.toCharArray();

                // Try changing each character to every letter a-z
                for (int j = 0; j < chars.length; j++) {
                    char original = chars[j];

                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == original) continue;
                        chars[j] = c;
                        String next = new String(chars);

                        if (next.equals(endWord)) return steps;

                        if (wordSet.contains(next) && !visited.contains(next)) {
                            visited.add(next);
                            queue.offer(next);
                        }
                    }

                    chars[j] = original;  // Restore
                }
            }
        }

        return 0;   // No transformation found
    }

    public static void main(String[] args) {
        System.out.println(ladderLength("hit", "cog",
            Arrays.asList("hot","dot","dog","lot","log","cog")));  // 5
        System.out.println(ladderLength("hit", "cog",
            Arrays.asList("hot","dot","dog","lot","log")));         // 0
    }
}

Output:
5
0

Dry Run: Word Ladder `hit → cog`

wordSet = {hot, dot, dog, lot, log, cog}
queue = [(hit, steps=1)], visited = {hit}

Level 1 (steps=1 → steps becomes 2):
  Word: hit
  Try h→a..z: no match; Try i→o: hot ∈ wordSet, not visited
    → visited.add(hot), queue=[hot]

Level 2 (steps=2 → steps becomes 3):
  Word: hot
  Try h→d: dot ∈ wordSet → queue=[dot]
  Try h→l: lot ∈ wordSet → queue=[dot,lot]

Level 3 (steps=3 → steps becomes 4):
  Word: dot
  Try d→l: lot already visited
  Try o→o... t→g: dog ∈ wordSet → queue=[lot,dog]
  Word: lot
  Try l→d: dot already visited
  Try t→g: log ∈ wordSet → queue=[lot,dog,log]

Level 4 (steps=4 → steps becomes 5):
  Word: dog
  Try d→c: cog == endWord! → return steps=5 ✓

Path: hit → hot → dot → dog → cog (5 words = 5 steps)

BFS Complexity Summary

Problem	Time	Space	BFS Variant
Level-order traversal	O(n)	O(w) max level width	Single-source, tree
Shortest path (graph)	O(V + E)	O(V)	Single-source, graph
Rotting oranges	O(rows × cols)	O(rows × cols)	Multi-source grid BFS
01 Matrix	O(rows × cols)	O(rows × cols)	Multi-source grid BFS
Word Ladder	O(N × M × 26)	O(N × M)	Single-source word graph

N = word list size, M = word length, 26 = alphabet size.

Common Mistakes

Marking visited on dequeue instead of enqueue. The same node can be enqueued multiple times from different neighbours before it is ever dequeued. When finally dequeued, it processes each neighbour again — O(E) redundant work and potentially wrong distance values. Always mark visited (or update distance) at the moment of enqueueing.

Not using levelSize for level boundaries. Processing children directly inside the loop without recording levelSize = queue.size() at the start mixes levels — children are processed at the same step as their parents. Record the count before the inner loop; dequeue exactly that many nodes.

Forgetting to seed all sources for multi-source BFS. Multi-source BFS requires all source nodes to be in the queue at the start, all at distance 0. Seeding only one source and running BFS, then another, is both incorrect and O(S × (V+E)) instead of O(V+E).

Not checking grid bounds before accessing grid[nr][nc]. Accessing grid[-1][0] or grid[rows][0] is undefined behavior in C++ and an IndexError in Python/Java. Always check nr >= 0 && nr < rows && nc >= 0 && nc < cols before reading or writing the grid.

Using Array.shift() inside BFS in JavaScript. shift() is O(n) — in a BFS over n nodes this gives O(n²). Use an index pointer qi advancing through the array, or use a proper O(1) queue implementation for large inputs.

Interview Questions

Q: Why does BFS guarantee the shortest path in an unweighted graph but not in a weighted one?

In an unweighted graph, all edges have equal cost. BFS processes nodes in non-decreasing distance order — first all nodes at distance 1, then distance 2, and so on. The first time a node is reached, it is via the fewest edges. In a weighted graph, a path with more edges can be shorter in total weight — BFS does not account for edge weights and may miss the shortest path. Dijkstra's algorithm uses a priority queue to always process the globally cheapest unvisited node, correctly handling varying edge weights.

Q: What is multi-source BFS and when is it more efficient than running BFS from each source?

Multi-source BFS initialises the queue with all source nodes at distance 0 simultaneously and runs a single BFS pass. This computes the shortest distance from the nearest source to every node in O(V + E). Running individual BFS from each of k sources takes O(k × (V + E)). For problems like "distance to nearest 0" or "time until all oranges rot," multi-source BFS is optimal. It is equivalent to adding a virtual super-source connected to all real sources with zero-weight edges.

Q: How do you track the actual shortest path (not just its length) in BFS?

Maintain a parent map alongside the distance map. When a node neighbour is first reached from node, set parent[neighbour] = node. After the BFS completes, reconstruct the path by following parent pointers backward from the target to the source, then reversing. The parent map uses O(V) additional space.

FAQs

Can BFS detect cycles in a graph?

Yes. When a neighbour of the current node is already in the visited set (and is not the parent in an undirected graph), a cycle exists. For directed graphs, any back edge to an already-visited node indicates a cycle. BFS is less commonly used for cycle detection than DFS — DFS naturally reveals back edges during its recursive structure — but BFS can detect cycles correctly.

Is BFS always better than DFS for shortest paths?

BFS finds the shortest path (fewest edges) in unweighted graphs and is preferred for that purpose. DFS is better for: detecting cycles, topological sort, finding all connected components, and problems requiring complete path exploration. For weighted shortest paths, neither BFS nor DFS is appropriate — use Dijkstra (non-negative weights) or Bellman-Ford (negative weights).

What is bidirectional BFS and when does it help?

Bidirectional BFS runs two simultaneous BFS explorations — one from the source, one from the target. They meet somewhere in the middle. If the shortest path has length d, standard BFS explores O(b^d) nodes (b = branching factor). Bidirectional BFS explores O(2 × b^(d/2)) nodes — exponentially fewer for large d. It is used in the Word Ladder problem and social network shortest paths where the graph is large but well-connected.

Summary

BFS uses a queue's FIFO property to explore a graph layer by layer — guaranteed to find the shortest path (fewest edges) in unweighted graphs.

The canonical BFS template:

›Initialise queue with source(s) at distance 0
›Mark visited on enqueue (not dequeue) to prevent redundant processing
›For each dequeued node, process it and enqueue all unvisited neighbours
›Level boundaries tracked by recording levelSize = queue.size() before each inner loop

Five core applications:

›Level-order traversal — record levelSize before inner loop; process that many nodes exactly; all their children form the next level
›Shortest path — standard single-source BFS; parent map reconstructs the actual path
›Rotting oranges / 01 matrix — multi-source BFS; seed all sources at distance 0; BFS fans out simultaneously
›Word Ladder — word graph BFS; generate neighbours by substituting each character position with a-z
›Dijkstra — priority queue replaces plain queue; processes by minimum distance, not by level