Level Order Traversal
Level order traversal (breadth-first search) visits nodes level by level from top to bottom, left to right. It uses a queue to process nodes in order of their depth.
Algorithm:
1. Push root into queue.
2. While queue not empty: pop node, print it, push its left and right children.
3. Repeat until queue empty.
Java implementation:
public void levelOrder(TreeNode root) {
if (root == null) return;
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
For printing each level separately, capture the queue size before processing the level:
public void levelOrderLevels(TreeNode root) {
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
System.out.println(); // new line after each level
}
}
Two Minute Drill
- Level order traversal uses a queue (BFS).
- Visits nodes by depth, left to right.
- Time O(n), space O(n) for queue.
- Useful for finding minimum depth, checking completeness, etc.
Need more clarification?
Drop us an email at career@quipoinfotech.com