Topic 65 of 78
Level Order
Overview
Breadth-First Search on a Tree (also called Level Order Traversal) explores the tree layer by layer, from top to bottom, left to right. It guarantees that you process all nodes at depth 1 before moving to depth 2. This is essential when you need to find the shortest path from the root to a leaf, or when printing a tree level by level.
Syntax
Since a tree flows strictly downward (no cycles), we don't need a `visited` set like we do in a general Graph BFS.
Level Order Traversal
java
public void levelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
System.out.print(current.val + " ");
if (current.left != null) queue.offer(current.left);
if (current.right != null) queue.offer(current.right);
}
}Common Pitfalls
- Adding null children to the queue. Always check `if (node.left != null)` before offering.
Interview Tips
- Tree BFS uses a Queue. Always check if the root is null before initializing the queue.
Real-World Example
Serializing a tree into an array (like LeetCode does under the hood) uses Level Order Traversal.
example
java
// Processing layer by layer
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
// process curr...
}