Definition
- Level Order Traversal – visits a binary tree breadth-first, one level at a time, from top to bottom and left to right within each level.
- Queue-based BFS – enqueue the root, then repeatedly dequeue all nodes at the current level, collect their values, and enqueue their children.
- Size snapshot – at the start of each level, record
queue.size()and process exactly that many nodes to cleanly separate levels. - Complexity – O(n) time; space proportional to the maximum width of the tree.
- Variants – zigzag order, right-side view, per-level averages, and per-level max all build on this base pattern.
Rajesh wants to read the National Bank of India org chart rank by rank: first the branch manager alone, then all direct reports together, then all of their reports together. He keeps a line of people to visit. He notes how many are in the line right now, processes exactly that many as one rank, and as he does he adds each person's reports to the back of the line for the next rank.
Understanding the Concepts
What is level order traversal?
Level order traversal visits every node in a binary tree from top to bottom, processing all nodes at the same depth before moving deeper. Within each level, nodes are visited left to right. The result is a list of lists, where each inner list contains the values of one level.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
public class LevelOrderTraversal {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int v) { val = v; }
}
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();
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;
}
public static void main(String[] args) {
// Build tree: 1
// / \
// 2 3
// / \ \
// 4 5 6
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(6);
System.out.println(levelOrder(root));
}
}
[[1], [2, 3], [4, 5, 6]]
Why does BFS use a queue?
Breadth-first search visits nodes in the order they were discovered, which is exactly FIFO behavior. The root is discovered first, then its children, then their children. A queue processes them in that discovery order. Using a stack instead would give depth-first order.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Queue;
public class WhyQueue {
public static void main(String[] args) {
Queue<String> bfs = new ArrayDeque<>();
bfs.offer("Root: Branch Manager");
bfs.offer("Level 1: Loan Officer");
bfs.offer("Level 1: Teller Lead");
System.out.println("BFS order (FIFO):");
while (!bfs.isEmpty()) {
System.out.println(" " + bfs.poll());
}
}
}
BFS order (FIFO):
Root: Branch Manager
Level 1: Loan Officer
Level 1: Teller Lead
How does the size snapshot separate levels?
At the start of each outer iteration, queue.size() tells you exactly how many nodes belong to the current level. You process that many nodes and no more. While processing, you enqueue children, which belong to the next level. Because you only dequeue the snapshot count, the children wait in the queue for the next iteration.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Queue;
public class SizeSnapshot {
public static void main(String[] args) {
Queue<String> queue = new ArrayDeque<>();
queue.offer("A"); // level 0
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size(); // snapshot
System.out.println("Level " + level + " has " + size + " nodes");
for (int i = 0; i < size; i++) {
String node = queue.poll();
System.out.println(" Processing: " + node);
// Simulate adding children
if (node.equals("A")) { queue.offer("B"); queue.offer("C"); }
if (node.equals("B")) { queue.offer("D"); }
}
level++;
}
}
}
Level 0 has 1 nodes
Processing: A
Level 1 has 2 nodes
Processing: B
Processing: C
Level 2 has 1 nodes
Processing: D
What are the edge cases?
An empty tree (null root) returns an empty list. A single-node tree returns one level with one element. A left-skewed or right-skewed tree returns one node per level. The algorithm handles all of these because the size snapshot adapts to however many nodes exist at each depth.
package com.bank.service;
public class LevelOrderEdgeCases {
static class TreeNode {
int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}
public static void main(String[] args) {
// Null root
System.out.println("Null: " + LevelOrderTraversal.levelOrder(null));
// Single node
System.out.println("Single: " + LevelOrderTraversal.levelOrder(new LevelOrderTraversal.TreeNode(42)));
// Skewed
LevelOrderTraversal.TreeNode skewed = new LevelOrderTraversal.TreeNode(1);
skewed.left = new LevelOrderTraversal.TreeNode(2);
skewed.left.left = new LevelOrderTraversal.TreeNode(3);
System.out.println("Skewed: " + LevelOrderTraversal.levelOrder(skewed));
}
}
Null: []
Single: [[42]]
Skewed: [[1], [2], [3]]
What are the common BFS variants?
Zigzag level order alternates left-to-right and right-to-left between levels. Right-side view collects only the last node of each level. Per-level average computes the mean value per level. All of these reuse the same size-snapshot queue loop and differ only in what they collect from each level.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Collections;
public class BfsVariants {
static class TreeNode {
int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}
// Zigzag: reverse odd-numbered levels
public static List<List<Integer>> zigzag(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode n = queue.poll();
level.add(n.val);
if (n.left != null) queue.offer(n.left);
if (n.right != null) queue.offer(n.right);
}
if (!leftToRight) Collections.reverse(level);
result.add(level);
leftToRight = !leftToRight;
}
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.right = new TreeNode(6);
System.out.println("Zigzag: " + zigzag(root));
}
}
Zigzag: [[1], [3, 2], [4, 5, 6]]
What about time and space complexity?
Time is O(n) because every node is enqueued and dequeued exactly once. Space is O(w) where w is the maximum width of the tree, because the queue at its fullest holds one entire level. For a balanced binary tree, the widest level has roughly n/2 nodes.
package com.bank.core;
public class BfsComplexity {
public static void main(String[] args) {
System.out.println("Time: O(n) - each node enqueued and dequeued once");
System.out.println("Space: O(w) - queue holds one full level");
System.out.println("Balanced tree: widest level has ~n/2 nodes");
System.out.println("Skewed tree: widest level has 1 node -> O(1) space");
}
}
Time: O(n) - each node enqueued and dequeued once
Space: O(w) - queue holds one full level
Balanced tree: widest level has ~n/2 nodes
Skewed tree: widest level has 1 node -> O(1) space
How is this applied in banking?
At the National Bank of India, I used level order traversal to produce a rank-by-rank view of the loan approval hierarchy for the compliance dashboard. Reviewers see all approvers at the same authority level grouped together. The left-to-right ordering within each rank encodes seniority, and the queue-based traversal with a fixed count per level keeps both grouping and ordering correct.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
public class ApprovalHierarchy {
static class Approver {
String name;
List<Approver> reports = new ArrayList<>();
Approver(String n) { name = n; }
}
public static void printByRank(Approver root) {
Queue<Approver> queue = new ArrayDeque<>();
queue.offer(root);
int rank = 0;
while (!queue.isEmpty()) {
int size = queue.size();
System.out.print("Rank " + rank + ": ");
for (int i = 0; i < size; i++) {
Approver a = queue.poll();
System.out.print(a.name + " ");
for (Approver r : a.reports) queue.offer(r);
}
System.out.println();
rank++;
}
}
public static void main(String[] args) {
Approver gm = new Approver("Pankaj(GM)");
Approver mgr1 = new Approver("Rajesh(Mgr)");
Approver mgr2 = new Approver("Priya(Mgr)");
gm.reports.add(mgr1);
gm.reports.add(mgr2);
mgr1.reports.add(new Approver("Amit(Officer)"));
mgr2.reports.add(new Approver("Neha(Officer)"));
printByRank(gm);
}
}
Rank 0: Pankaj(GM)
Rank 1: Rajesh(Mgr) Priya(Mgr)
Rank 2: Amit(Officer) Neha(Officer)
What should a senior engineer know?
The size-snapshot technique is the single most important BFS pattern to internalize. Almost every level-aware tree problem, from zigzag to right-side view to level sums, reuses the exact same outer loop with only the inner collection logic changed. Recognizing this pattern lets you solve an entire family of problems from a single template.
package com.bank.core;
public class SeniorBfsNotes {
public static void main(String[] args) {
System.out.println("Template: while (!queue.isEmpty()) { int size = queue.size(); ... }");
System.out.println("Variant: zigzag -> reverse alternate levels");
System.out.println("Variant: right-side view -> take last node of each level");
System.out.println("Variant: level averages -> sum and divide per level");
System.out.println("All share the same size-snapshot outer loop");
}
}
Template: while (!queue.isEmpty()) { int size = queue.size(); ... }
Variant: zigzag -> reverse alternate levels
Variant: right-side view -> take last node of each level
Variant: level averages -> sum and divide per level
All share the same size-snapshot outer loop
Visual Overview
Level Order Traversal
─────────────────────
Tree: 1
/ \
2 3
/ \ \
4 5 6
Queue walk:
┌───────────────────────────────────────────┐
│ Start: queue = [1] │
│ │
│ Level 0: size=1, process [1] │
│ enqueue children: [2, 3] │
│ output: [1] │
│ │
│ Level 1: size=2, process [2, 3] │
│ enqueue children: [4, 5, 6] │
│ output: [2, 3] │
│ │
│ Level 2: size=3, process [4, 5, 6] │
│ no children │
│ output: [4, 5, 6] │
│ │
│ Queue empty → done │
└───────────────────────────────────────────┘
Result: [[1], [2, 3], [4, 5, 6]]
Key Takeaway
Level order traversal is breadth-first: I visit every node at the same depth before moving deeper, using a FIFO queue. The single technique that separates levels cleanly is snapshotting queue.size() at the start of each outer iteration and dequeuing exactly that many nodes. While processing, I enqueue their children, which belong to the next level and wait in the queue until the current level is done.
The time complexity is O(n) because every node is enqueued and dequeued once. The space is proportional to the maximum width of the tree, since the queue at its fullest holds one entire level. For a balanced tree that can be roughly n/2 nodes, but for a skewed tree it is just 1.
This base pattern is the foundation for nearly every level-aware BFS variant. Zigzag order reverses alternate levels. Right-side view collects only the last node per level. Per-level averages sum and divide. All of them reuse the same size-snapshot loop and differ only in what they collect from each level.
In my project at the National Bank of India, I used this to produce a rank-by-rank view of the loan approval hierarchy, so compliance reviewers see all approvers at the same authority level grouped together. The left-to-right order within each rank encodes seniority, and the queue-based traversal with a fixed count per level keeps both grouping and ordering correct.
Remember one sentence: snapshot the queue size at each level, dequeue exactly that many nodes, and enqueue their children for the next level.
---