🔑 Core Idea of BFS:
- Use a Queue to process nodes level by level (FIFO order).
- In graphs, BFS ensures shortest path in an unweighted graph.
- In trees, BFS naturally produces level order traversal.
📝 Problem 1: Binary Tree Level Order Traversal
👉 Amazon phrasing:
Given a binary tree, return its nodes level by level.
Java Solution
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class LevelOrderTraversal {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; 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;
}
}
✅ Time Complexity: O(n)
✅ Space Complexity: O(n)
📝 Problem 2: Zigzag Level Order Traversal
👉 Amazon phrasing:
Return nodes in zigzag order: left→right, then right→left, etc.
Java Solution
public class ZigzagTraversal {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int size = queue.size();
LinkedList<Integer> level = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (leftToRight) {
level.addLast(node.val);
} else {
level.addFirst(node.val);
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
leftToRight = !leftToRight;
}
return result;
}
}
✅ Twist of Level Order by deque insertion.
📝 Problem 3: Binary Tree Right Side View
👉 Amazon phrasing:
Return the values of nodes visible from the right side.
Java Solution
public class RightSideView {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == size - 1) result.add(node.val); // rightmost
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return result;
}
}
✅ Trick: last node at each level = rightmost view.
📝 Problem 4: Connect Next Right Pointers
👉 Amazon phrasing:
Given a perfect binary tree, connect each node to its next right node.
Java Solution
class Node {
int val;
Node left, right, next;
Node(int x) { val = x; }
}
public class ConnectNextPointers {
public Node connect(Node root) {
if (root == null) return null;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
Node prev = null;
for (int i = 0; i < size; i++) {
Node node = queue.poll();
if (prev != null) prev.next = node;
prev = node;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return root;
}
}
✅ Very popular Amazon favorite.
📝 Problem 5: Shortest Path in an Unweighted Graph (BFS)
👉 Amazon phrasing:
Given an undirected graph, find the shortest path between two nodes.
Java Solution
public class ShortestPath {
public int shortestPath(Map<Integer, List<Integer>> graph, int src, int dest) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(src);
visited.add(src);
int distance = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int node = queue.poll();
if (node == dest) return distance;
for (int nei : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(nei)) {
visited.add(nei);
queue.offer(nei);
}
}
}
distance++;
}
return -1;
}
}
✅ BFS guarantees minimum steps in an unweighted graph.
📝 Problem 6: Rotten Oranges (Grid BFS)
👉 Amazon phrasing:
Each orange is either fresh (1) or rotten (2). Every minute, rotten oranges spread to adjacent fresh ones. Return min time until all are rotten.
Java Solution
public class RottenOranges {
public int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
// Step 1: collect rotten & count fresh
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) queue.offer(new int[]{r, c});
if (grid[r][c] == 1) fresh++;
}
}
int minutes = 0;
int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
// Step 2: BFS
while (!queue.isEmpty() && fresh > 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
fresh--;
queue.offer(new int[]{nr, nc});
}
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}
}
✅ Classic multi-source BFS.
📚 Extended Amazon BFS Problems
- Word Ladder (LeetCode 127) – Shortest transformation sequence
- Course Schedule (LeetCode 207) – Topological sort via BFS
- Clone Graph (LeetCode 133) – BFS + hashmap
- Island Problems (DFS/BFS hybrid) – Count islands, max area of island
- Minimum Knight Moves (chessboard BFS)
🎯 Key Takeaways
- BFS is best for shortest path and level order style problems.
- Queue is the backbone → think in layers.
- Amazon often twists BFS into grids, graphs, and tree variations.
📅 Next in the series (Day 8):
👉 DFS + Backtracking Pattern – Subsets, permutations, N-Queens, word search, and Amazon’s “Letter Combinations of a Phone Number”.
Top comments (0)