Breadth-First Search: Level-Order Traversal & Tree Diameter
Master horizontal tree traversals. Learn Breadth-First Search (BFS) using a Queue, level-by-level batching, zig-zag traversals, and calculating tree diameter.
By the end, you’ll be able to…
- Implement Breadth-First Search (BFS) Level-Order Traversal using a Queue in O(N) time.
- Batch nodes level-by-level using the queue size snapshot pattern.
- Calculate the Diameter of a Binary Tree using bottom-up post-order DFS.
01Breadth-First Search (BFS) Mechanics
While Depth-First Search (DFS) explores as deep as possible along a single branch before backtracking, Breadth-First Search (BFS) explores the tree horizontally, visiting all nodes at depth 0, then all nodes at depth 1, then all nodes at depth 2, and so forth.
To achieve level-by-level traversal, BFS utilizes a Queue (FIFO buffer). The algorithm enqueues the root node. In a loop, it dequeues a node, processes it, and enqueues its non-null left and right children. Because queues operate in First-In, First-Out order, children of the current level wait behind all nodes of the current level.
02The Queue Size Snapshot Pattern
A crucial pattern in level-order traversal is int levelSize = queue.size(). Because new children are added to the queue during iteration, the queue size dynamically changes.
By taking a snapshot of queue.size() before entering the inner for-loop, we isolate exactly how many nodes belong to the CURRENT level. The inner loop dequeues exactly levelSize times, guaranteeing that all nodes of the current level are processed together as a distinct batch.
+---------------------------------------------------+| BFS Level-Order Queue Progression |+---------------------------------------------------+| Step 1: Queue: [ Root(3) ] | Level 0: [3]|| Step 2: Queue: [ Left(9), Right(20) ] | Level 1: [9, 20]| Step 3: Queue: [ L(15), R(7) ] | Level 2: [15, 7]+---------------------------------------------------+03The Diameter of a Binary Tree
The Diameter of a Binary Tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root node!
At any given node, the longest path passing through that node is: leftHeight + rightHeight. We solve this using a bottom-up post-order DFS: each node returns its height (1 + max(left, right)) to its parent, while simultaneously updating a global maximum diameter variable with (leftHeight + rightHeight).
04Why This Matters in Production
BFS is the fundamental algorithm for finding the Shortest Path in unweighted graphs and network topologies (such as finding the fewest hops between routers in computer networking, or degrees of separation in social networks).
In cloud clustering, BFS level-order inspection checks distributed node health in expanding concentric rings from a master orchestrator.
05Production Architecture & Engineering Trade-Offs
Tree-based data structures provide the foundational indexing mechanism for database storage engines and file systems. However, maintaining balanced tree topology under continuous insertion and deletion workloads is non-trivial. While perfectly balanced trees guarantee O(log n) worst-case search latencies, the rotational overhead required to enforce strict balance factors can degrade write performance.
In production database engines such as PostgreSQL or MySQL InnoDB, B+ Trees are favored over binary search trees because their high branching factor minimizes disk I/O and aligns node sizes with operating system virtual memory page boundaries. When operating entirely in memory, Red-Black trees offer an optimal compromise by bounding rebalancing rotations to a small constant number.
The ideas worth keeping.
- BFS traverses trees level-by-level using a FIFO Queue in linear O(N) time.
- Capture queue.size() as a snapshot to cleanly batch nodes by level.
- Tree diameter calculates leftHeight + rightHeight bottom-up at each node in O(N) time.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Zigzag Level Order Traversal
Modify levelOrder to alternate reading levels from left-to-right and right-to-left (Zigzag traversal) using a boolean flag.
Explore a worked solution
boolean leftToRight = true;// Inside level loop:if (leftToRight) currentLevel.add(node.val);else currentLevel.add(0, node.val); // Add to frontleftToRight = !leftToRight;Toggling the boolean flag and inserting at index 0 reverses order on alternating levels.
Exercise 2: Right Side View of Binary Tree
Explain how BFS level-order traversal extracts the Right Side View of a binary tree in O(N) time.
Explore a worked solution
In each level loop, when index i equals levelSize - 1 (the last element of that level), add node.val to the result list.The last node processed in each BFS level is the rightmost visible node from that perspective.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Zigzag Level Order Traversal
Modify levelOrder to alternate reading levels from left-to-right and right-to-left (Zigzag traversal) using a boolean flag.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.