![how-i-drove-400%-growth-in-client-activation-with-sedall-asante-[video]](https://prodsens.live/wp-content/uploads/2025/10/39802-how-i-drove-400-growth-in-client-activation-with-sedall-asante-video-80x80.png)
Traversal by levels (a.k.a. BFS) is another fundamental pattern.
Instead of depth-first recursion, we explore the tree level by level using a queue.
🔍 Identifying the Pattern
Use BFS (level order) when the problem mentions:
- Visiting nodes level by level (top-down / bottom-up).
- Finding shortest paths in trees.
- Grouping nodes by level or distance.
- Symmetry, completeness, or perfectness checks.
👉 Keywords: “level”, “distance”, “shortest”, “next pointer”, “zigzag”
🛠 Core Idea & Template
void bfs(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size(); // process one level
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
// Process node here
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
}
✅ Classic Problems & Java Solutions
1. Binary Tree Level Order Traversal (LC 102)
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
level.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
res.add(level);
}
return res;
}
}
2. Binary Tree Level Order Traversal II (Bottom-Up) (LC 107)
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
LinkedList<List<Integer>> res = new LinkedList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
level.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
res.addFirst(level); // only difference
}
return res;
}
}
3. Binary Tree Zigzag Level Order Traversal (LC 103)
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
boolean leftToRight = true;
while (!q.isEmpty()) {
int size = q.size();
LinkedList<Integer> level = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (leftToRight) level.addLast(node.val);
else level.addFirst(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
res.add(level);
leftToRight = !leftToRight;
}
return res;
}
}
4. Average of Levels in Binary Tree (LC 637)
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
double sum = 0;
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
sum += node.val;
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
res.add(sum / size);
}
return res;
}
}
5. Populating Next Right Pointers in Each Node (LC 116/117)
class Solution {
public Node connect(Node root) {
if (root == null) return null;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
Node prev = null;
for (int i = 0; i < size; i++) {
Node node = q.poll();
if (prev != null) prev.next = node;
prev = node;
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}
return root;
}
}
6. Minimum Depth of Binary Tree (LC 111)
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int depth = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (node.left == null && node.right == null) return depth;
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
depth++;
}
return depth;
}
}
7. Maximum Depth of Binary Tree (via BFS) (LC 104)
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int depth = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
depth++;
}
return depth;
}
}
🚀 Advanced Variations
- Vertical Order Traversal (group by column index).
- Diagonal Traversal.
- Right Side View (LC 199) / Left Side View.
- Cousins in Binary Tree.
🎯 Summary Checklist
When you see:
- “Level order”, “zigzag”, “average by level” → BFS with queue.
- “Minimum depth”, “shortest distance” → BFS is optimal.
- “Connect next pointer” → BFS with
prevtracking. - “Side view” → BFS but take first/last node per level.
👉 If distance/level/grouping matters → Think Level Order Traversal (BFS).
![[ml-story]-exploring-the-future-of-text-generation:-a-deep-dive-into-vertex-ai-using-jupyter…](https://prodsens.live/wp-content/uploads/2023/09/14631-ml-story-exploring-the-future-of-text-generation-a-deep-dive-into-vertex-ai-using-jupyter-380x229.png)
