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)Time & Space Complexity Common Mistakes 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

BFS / Level Order Traversal

What Is BFS on a Binary Tree?

Breadth-First Search (BFS) explores a binary tree level by level — visiting all nodes at depth k before any node at depth k+1. Unlike DFS which dives deep first, BFS fans out horizontally.

Reference tree for all examples:

              1                ← Level 0
            /   \
           2     3             ← Level 1
          / \   / \
         4   5 6   7           ← Level 2
        /
       8                       ← Level 3

BFS (level order) visits:  1 | 2 3 | 4 5 6 7 | 8
DFS (preorder) visits:     1 2 4 8 5 3 6 7

A queue (FIFO) is the key data structure. Nodes are enqueued when discovered and dequeued when processed. Because all nodes at one level are enqueued before any of their children, the FIFO property ensures level-by-level order automatically.

The Level-Boundary Trick

Most BFS problems require knowing where one level ends and the next begins. The cleanest technique: record the queue size before processing each level.

Queue state during BFS of the reference tree:

Start: queue = [1]

Level 0 — levelSize = 1:
  Dequeue 1 → enqueue 2, 3
  queue = [2, 3]    ← all level-0 children

Level 1 — levelSize = 2:
  Dequeue 2 → enqueue 4, 5
  Dequeue 3 → enqueue 6, 7
  queue = [4, 5, 6, 7]    ← all level-1 children

Level 2 — levelSize = 4:
  Dequeue 4 → enqueue 8
  Dequeue 5, 6, 7 → no children
  queue = [8]    ← all level-2 children

Level 3 — levelSize = 1:
  Dequeue 8 → no children
  queue = []    ← BFS complete

Standard Level Order Traversal

Java

import java.util.*;

public class LevelOrder {

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

    // 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();          // Nodes at this level
            List<Integer> level = new ArrayList<>();

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

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

            result.add(level);
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left  = new TreeNode(2); root.right = new TreeNode(3);
        root.left.left  = new TreeNode(4); root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6); root.right.right = new TreeNode(7);
        root.left.left.left = new TreeNode(8);

        System.out.println(levelOrder(root));
        // [[1], [2, 3], [4, 5, 6, 7], [8]]
    }
}

Output:
[[1], [2, 3], [4, 5, 6, 7], [8]]

Dry Run: Level Order on the Reference Tree

Tree:           1
              /   \
             2     3
            / \   / \
           4   5 6   7
          /
         8

queue=[1], result=[]

Level 0: levelSize=1
  Dequeue 1 → level=[1] → enqueue 2, 3
  result=[[1]], queue=[2,3]

Level 1: levelSize=2
  Dequeue 2 → level=[2] → enqueue 4, 5
  Dequeue 3 → level=[2,3] → enqueue 6, 7
  result=[[1],[2,3]], queue=[4,5,6,7]

Level 2: levelSize=4
  Dequeue 4 → level=[4] → enqueue 8
  Dequeue 5 → level=[4,5] → no children
  Dequeue 6 → level=[4,5,6] → no children
  Dequeue 7 → level=[4,5,6,7] → no children
  result=[[1],[2,3],[4,5,6,7]], queue=[8]

Level 3: levelSize=1
  Dequeue 8 → level=[8] → no children
  result=[[1],[2,3],[4,5,6,7],[8]], queue=[]

Final: [[1],[2,3],[4,5,6,7],[8]] ✓

Variation 1: Zigzag Level Order

Alternate the direction at each level — even levels (0, 2, 4…) left-to-right, odd levels (1, 3, 5…) right-to-left.

Reference tree zigzag traversal:

Level 0 (L→R):  [1]
Level 1 (R→L):  [3, 2]
Level 2 (L→R):  [4, 5, 6, 7]
Level 3 (R→L):  [8]

Result: [[1], [3, 2], [4, 5, 6, 7], [8]]

Java

import java.util.*;

public class ZigzagOrder {

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

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean leftToRight = true;         // Direction flag

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            LinkedList<Integer> level = new LinkedList<>(); // Supports addFirst

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

                if (leftToRight) {
                    level.addLast(node.val);   // Append to end
                } else {
                    level.addFirst(node.val);  // Prepend to front (reverses order)
                }

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

            result.add(level);
            leftToRight = !leftToRight;        // Flip direction
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left  = new TreeNode(2); root.right = new TreeNode(3);
        root.left.left  = new TreeNode(4); root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6); root.right.right = new TreeNode(7);
        root.left.left.left = new TreeNode(8);

        System.out.println(zigzagLevelOrder(root));
        // [[1], [3, 2], [4, 5, 6, 7], [8]]
    }
}

Output:
[[1], [3, 2], [4, 5, 6, 7], [8]]

Variation 2: Right Side View

Return the last node visible at each level when looking from the right. In standard BFS where children are enqueued left-before-right, the last dequeued node in each level is the rightmost.

Reference tree:           Right side view nodes:
         1                  Level 0: last = 1   → visible
       /   \
      2     3               Level 1: last = 3   → visible
     / \   / \
    4   5 6   7             Level 2: last = 7   → visible
   /
  8                         Level 3: last = 8   → visible

Right side view: [1, 3, 7, 8]

Java

import java.util.*;

public class RightSideView {

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

    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();

                // Last node in this level is visible from the right
                if (i == levelSize - 1) {
                    result.add(node.val);
                }

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

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left  = new TreeNode(2); root.right = new TreeNode(3);
        root.left.left  = new TreeNode(4); root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6); root.right.right = new TreeNode(7);
        root.left.left.left = new TreeNode(8);

        System.out.println(rightSideView(root)); // [1, 3, 7, 8]
    }
}

Output:
Right view: [1, 3, 7, 8]
Left view:  [1, 2, 4, 8]

Variation 3: Average of Levels

Compute the average value of nodes at each level.

Java

import java.util.*;

public class AverageOfLevels {

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

    public static List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if (root == null) return result;

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            double sum    = 0;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                sum += node.val;                  // Accumulate sum

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

            result.add(sum / levelSize);          // Average for this level
        }

        return result;
    }

    public static void main(String[] args) {
        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(averageOfLevels(root));
        // [3.0, 14.5, 11.0]
        // Level 0: 3/1=3.0
        // Level 1: (9+20)/2=14.5
        // Level 2: (15+7)/2=11.0
    }
}

Output:
[3.0, 14.5, 11.0]

Variation 4: Bottom-Up Level Order

Return levels from the deepest level up to the root. The simplest approach: run standard BFS, then reverse the result list.

Reference tree:
         1
       /   \
      2     3
     / \   / \
    4   5 6   7
   /
  8

Standard top-down:  [[1], [2,3], [4,5,6,7], [8]]
Bottom-up (reversed): [[8], [4,5,6,7], [2,3], [1]]

Java

import java.util.*;

public class BottomUpLevelOrder {

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

    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>(); // addFirst is O(1)
        if (root == null) return result;

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            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.addFirst(level);   // Prepend — deepest level ends up at index 0
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left  = new TreeNode(2); root.right = new TreeNode(3);
        root.left.left  = new TreeNode(4); root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6); root.right.right = new TreeNode(7);
        root.left.left.left = new TreeNode(8);

        System.out.println(levelOrderBottom(root));
        // [[8], [4, 5, 6, 7], [2, 3], [1]]
    }
}

Output:
[[8], [4, 5, 6, 7], [2, 3], [1]]

Variation 5: Maximum Width of Binary Tree

The width of a level is the number of positions between the leftmost and rightmost nodes (including null positions in between).

Tree:           1
              /   \
             2     3
            / \     \
           4   5     7

Level 0: [1]         → width = 1
Level 1: [2, 3]      → width = 2
Level 2: [4, 5, _, 7] → width = 4 (positions 0,1,2,3; null at position 2)

Maximum width = 4

The key insight: assign position indices to nodes like a complete binary tree. If parent is at index i, left child is at 2i and right child is at 2i+1. Width at any level = rightmost_index - leftmost_index + 1.

Java

import java.util.*;

public class MaxWidth {

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

    public static int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;

        int maxWidth = 0;
        // Queue stores (node, column_index)
        Queue<long[]> queue = new ArrayDeque<>(); // [node_ref_as_index, col]
        Queue<TreeNode> nodeQueue = new ArrayDeque<>();

        nodeQueue.offer(root);
        queue.offer(new long[]{0});   // Root at index 0

        while (!nodeQueue.isEmpty()) {
            int levelSize = nodeQueue.size();
            long firstIdx = queue.peek()[0];
            long lastIdx  = firstIdx;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = nodeQueue.poll();
                long idx = queue.poll()[0] - firstIdx;   // Normalise to prevent overflow
                lastIdx = idx;

                if (node.left  != null) {
                    nodeQueue.offer(node.left);
                    queue.offer(new long[]{2 * idx});
                }
                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    queue.offer(new long[]{2 * idx + 1});
                }
            }

            maxWidth = (int) Math.max(maxWidth, lastIdx - 0 + 1);
        }

        return maxWidth;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left  = new TreeNode(2); root.right = new TreeNode(3);
        root.left.left  = new TreeNode(4); root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(7);

        System.out.println(widthOfBinaryTree(root));  // 4
    }
}

Output:
4

BFS Variations Summary

VARIATION          KEY CHANGE FROM STANDARD BFS        RESULT
───────────────────────────────────────────────────────────────────
Standard           Collect all nodes per level           [[1],[2,3],[4,5,6,7]]
Zigzag             Toggle addLast/addFirst each level    [[1],[3,2],[4,5,6,7]]
Right side view    Record last node per level            [1, 3, 7, 8]
Left side view     Record first node per level           [1, 2, 4, 8]
Average of levels  Compute sum/count per level           [1.0, 2.5, 5.5, 8.0]
Bottom-up          Reverse the final result list         [[8],[4,5,6,7],[2,3],[1]]
Max width          Track column indices per node         4

Complexity Summary

Operation	Time	Space	Notes
Level order	O(n)	O(w)	w = max level width ≤ n/2 for perfect tree
Zigzag	O(n)	O(w)	deque addFirst is O(1)
Right/left side view	O(n)	O(w)	Only collect last/first node per level
Average of levels	O(n)	O(w)	Sum and count per level
Bottom-up	O(n)	O(n)	O(n) to reverse the result
Max width	O(n)	O(w)	Normalise indices to prevent overflow

Common Mistakes

Using queue.length inside the inner for-loop. The queue size changes as children are enqueued. Always capture levelSize = queue.size() BEFORE the inner loop and use that fixed value. Using queue.length inside the loop means the boundary shifts as children are added — nodes from the next level are processed in the current level.

Integer overflow in max-width with large sparse trees. Node column indices are computed as 2*i and 2*i+1. For a tree of height 30+, these indices can exceed 32-bit integer range. Always use long (Java/C++), arbitrary-precision Python integers, or BigInt (JavaScript). Normalise by subtracting the first index of each level to keep values small.

Calling queue.shift() in the inner loop for large JavaScript arrays. Array.shift() is O(n) — using it for BFS on large trees gives O(n²) total. Use a pointer index (qi++) instead of shift, or use a proper deque/linked-list implementation. Python's collections.deque.popleft() is O(1).

Zigzag: adding node.val directly vs inserting at index 0. Both approaches work but unshift / addFirst is cleaner than collecting the level and reversing afterwards. For the deque approach, the enqueue order does NOT change — only the insertion order into the level list changes based on the direction flag.

Interview Questions

Q: What is the time and space complexity of level order traversal?

O(n) time — each of the n nodes is enqueued exactly once and dequeued exactly once. O(w) space for the queue, where w is the maximum level width. For a perfect binary tree, the last level has n/2 nodes, so w = O(n) in the worst case. The result list is additionally O(n) space. Overall: O(n) time and O(n) space.

Q: How does zigzag traversal differ from standard level order?

Standard level order collects each level left-to-right. Zigzag alternates: even levels are collected left-to-right, odd levels right-to-left. The implementation uses the same BFS logic with a direction flag. When right-to-left, nodes are inserted at the front of the level list (using addFirst or unshift) instead of appended at the end. The queue itself is never reversed — only the collection order changes.

Q: Why do we subtract the leftmost index (normalise) in the maximum width calculation?

Node indices follow complete binary tree indexing: left child = 2i, right child = 2i+1. For a right-skewed tree of depth h, a node can have index 2^h which overflows 32-bit integers. Normalising by subtracting the leftmost index of each level keeps all indices small — the relative positions are preserved but absolute values are bounded by the level width, preventing overflow.

Summary

BFS on a binary tree uses a queue to process nodes level by level. The FIFO property ensures all nodes at depth k are processed before any node at depth k+1.

The level-boundary technique: capture levelSize = queue.size() before the inner loop; dequeue exactly levelSize nodes per level; their children form the next level.

Six BFS variations — all built on the same core template:

Variation	One-line change
Standard level order	Collect all node values per level
Zigzag	Toggle `addFirst` / `addLast` with a direction flag
Right side view	Record only the last node per level (`i == levelSize - 1`)
Left side view	Record only the first node per level (`i == 0`)
Average of levels	Sum node values, divide by levelSize
Bottom-up	Run standard BFS, reverse the result list
Max width	Attach column indices to queue entries, normalise per level

In the next topic you will explore Height, Depth, and Diameter — computing the height of a tree, finding the diameter (longest path between any two nodes), and related depth-based problems.

Suggested Quiz

What data structure does BFS use to process nodes level by level?

1/6

←

PreviousBinary Tree DFS Traversals

NextBinary Tree Operations

→