DSA Patterns Made Simple · Trees and Graphs
Tree BFS: Level by Level
Process a tree one level at a time with a queue. Use it for level-order output, the right-side view, the minimum depth, and anything that says 'level' or 'closest'.
The problem
Binary Tree Level Order Traversal: return the values level by level: [[3], [9, 20], [15, 7]]. Depth-first search dives down one branch before the others, so levels get mixed up. You need to finish each level before starting the next.
How to spot it
- The word level: level order, average of each level, largest value per level, zigzag
- "Right side view" (the last node of each level)
- Minimum depth, or the closest/nearest node (BFS reaches near things first)
The idea
Use a queue (first in, first out), like people boarding by row number. Start with the root. Repeat: note how many nodes are in the queue right now (that's one full level), take exactly that many out, record them, and add their children to the back of the queue.
The template
from collections import deque
queue = deque([root]) if root else deque()
while queue:
level = []
for _ in range(len(queue)): # exactly one level
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
handle(level)
let queue = root ? [root] : [];
while (queue.length) {
const level = [], next = [];
for (const node of queue) { // exactly one level
level.push(node.val);
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
handle(level);
queue = next;
}
In JavaScript, array.shift() is O(n), so the template builds the next level in a new array instead. Python's deque.popleft() is O(1).
Worked example
Level order, right-side view and minimum depth, all from the same loop.
from collections import deque
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def build(values):
"""Level-order list (None = no child), like the pictures in problem statements."""
nodes = [Node(v) if v is not None else None for v in values]
kids = nodes[1:]
for node in nodes:
if node:
node.left = kids.pop(0) if kids else None
node.right = kids.pop(0) if kids else None
return nodes[0] if nodes else None
def levels(root):
out = []
queue = deque([root]) if root else deque()
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
out.append(level)
return out
def right_side_view(root):
return [level[-1] for level in levels(root)]
def min_depth(root):
depth = 0
queue = deque([root]) if root else deque()
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
if not node.left and not node.right:
return depth # first leaf found is the closest one
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return 0
tree = build([3, 9, 20, None, None, 15, 7])
print("levels:", levels(tree))
print("right side:", right_side_view(build([1, 2, 3, None, 5, None, 4])))
print("min depth:", min_depth(tree))
Output
levels: [[3], [9, 20], [15, 7]] right side: [1, 3, 4] min depth: 2
class Node {
constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
}
function build(values) {
// Level-order list (null = no child), like the pictures in problem statements.
const nodes = values.map((v) => (v === null ? null : new Node(v)));
const kids = nodes.slice(1);
for (const node of nodes) {
if (node) {
node.left = kids.length ? kids.shift() : null;
node.right = kids.length ? kids.shift() : null;
}
}
return nodes[0] ?? null;
}
function levels(root) {
const out = [];
let queue = root ? [root] : [];
while (queue.length) {
const level = [], next = [];
for (const node of queue) {
level.push(node.val);
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
out.push(level);
queue = next;
}
return out;
}
function rightSideView(root) {
return levels(root).map((level) => level.at(-1));
}
function minDepth(root) {
let depth = 0;
let queue = root ? [root] : [];
while (queue.length) {
depth++;
const next = [];
for (const node of queue) {
if (!node.left && !node.right) return depth; // first leaf found is the closest one
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
queue = next;
}
return 0;
}
const show = (v) => JSON.stringify(v).replaceAll(",", ", ");
const tree = build([3, 9, 20, null, null, 15, 7]);
console.log("levels:", show(levels(tree)));
console.log("right side:", show(rightSideView(build([1, 2, 3, null, 5, null, 4]))));
console.log("min depth:", minDepth(tree));
Output
levels: [[3], [9, 20], [15, 7]] right side: [1, 3, 4] min depth: 2
Common mistakes
- Reading
len(queue)inside the loop while adding children; capture the level size first (or build anextlist). - Using DFS for minimum depth. DFS must explore the whole tree; BFS stops at the first leaf.
shift()in big JavaScript queues, which makes BFS O(n²). Swap arrays per level or keep a head index.- Pushing
nullchildren and then crashing onnull.val.
Practice
- Binary Tree Level Order Traversal (medium)
Key points
- BFS = queue; one level per outer loop iteration.
- Use it for anything with "level", "nearest" or "minimum depth".
- Capture the level size before adding children.
- O(n) time, O(w) space for the widest level w.
Practice questions
When would you choose BFS over DFS on a tree?
Answer
When the problem is about levels (level order, right side view, per-level averages) or the nearest/minimum (minimum depth): BFS visits nodes in order of distance from the root and can stop at the first match.
How do you keep BFS levels separate?
Answer
Before processing a level, record how many nodes are in the queue (or collect children into a separate 'next' list); process exactly that many, then start the next level.
Open in the app to mark lessons complete, take notes and track your progress.