Tree BFS
On this page
Breadth-first search uses a queue: take a node from the front, add its children to the back. Nodes come out in order of depth, so BFS is the natural tool whenever a question talks about levels, or wants the node closest to the root. One small trick turns the plain traversal into a level-by-level one, and nearly every tree BFS question builds on it.
When to recognise it
- The word level appears: level order, average of each level, largest value per level, zigzag.
- "What you see from the right / left side": the last (or first) node of each level.
- Minimum depth, the nearest leaf, the shortest path in an unweighted tree: BFS can stop at the first hit.
- Connect each node to its right neighbour, or anything about neighbours on the same level.
- Width of a tree, or numbering nodes by position in each level.
How it works
At the start of a round, every node in the queue belongs to the same level. Read len(queue) once, pop exactly that many nodes, and push their children. The children wait for the next round.
![A tree with root 1, children 2 and 3, grandchildren 4, 5, 6, colored by level. A table shows three rounds: size 1 pops 1, size 2 pops 2 and 3, size 3 pops 4, 5, 6. The right side view is [1, 3, 6].](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-da04e22e.png)
Template
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
def level_order(root):
"""Queue + level size: everything in the queue at the start of a round is one level."""
if not root:
return []
out, q = [], deque([root])
while q:
level = []
for _ in range(len(q)): # freeze the size BEFORE adding children
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
out.append(level)
return out
Time O(n). Space O(w), where w is the widest level, up to about n/2 in a full tree. Use collections.deque; list.pop(0) is O(n) per pop.
Once you have levels, many questions are one line:
def right_side_view(root):
return [level[-1] for level in level_order(root)]
def zigzag(root):
return [lvl if i % 2 == 0 else lvl[::-1] for i, lvl in enumerate(level_order(root))]
In an interview, it is often better to compute the answer inside the loop (for example, record the last node of each round) instead of building all levels first. Both are O(n); say which one you are doing.
Stopping early
BFS reaches shallow nodes first, so for minimum depth you can return at the first leaf. DFS would have to explore every branch to be sure.
from collections import deque
def min_depth(root):
"""BFS stops at the FIRST leaf it meets, so it never explores deeper levels."""
if not root:
return 0
q = deque([(root, 1)])
while q:
node, d = q.popleft()
if not node.left and not node.right:
return d
for c in (node.left, node.right):
if c:
q.append((c, d + 1))
BFS or DFS?

Both visit every node once. Choose by the question: levels and "nearest" point to BFS; subtree facts and paths point to Tree DFS. Right side view can be done either way (DFS visiting right first and recording the first node at each new depth), and that is a good follow-up answer.
Common bugs
- Calling
len(queue)inside the inner loop, or usingwhile queueas the inner loop, which mixes levels. - Pushing
Nonechildren and then crashing onnode.val. Check before pushing. - Using a list as the queue, which turns
pop(0)into O(n) and the whole thing into O(n²). - Empty tree: return
[](or 0) before touchingroot. - Zigzag by inserting at the front of a Python list: that is O(n) per insert. Reverse the finished level, or use a deque per level.
Say this in the interview
- "I take the queue's size at the start of each round. Exactly those nodes form the current level; their children belong to the next one."
- "BFS finds the shallowest leaf first, so for minimum depth I can stop early instead of exploring the whole tree."
Problems for this pattern
- Average of Levels in Binary Tree: the level template with a sum.
- Binary Tree Level Order Traversal: the template.
- Binary Tree Right Side View: last node per round.
- Binary Tree Zigzag Level Order Traversal: reverse every other level.
- Binary Tree Vertical Order Traversal: BFS with a column number.
- All Nodes Distance K in Binary Tree: add parent links, then BFS from the target.
- Serialize and Deserialize Binary Tree: level order (or pre-order) with null markers.
Related
Binary Trees · Tree DFS · Graph BFS and DFS (the same queue on a graph) · Stacks and Queues