What does it solve?
Breadth-First Search visits a tree level by level using a queue. Push the root, then repeatedly pop a node and enqueue its children. The trick that unlocks every variant: at the top of each loop, snapshot the current queueSize. That count is exactly how many nodes sit on the current level, so you can process a whole level in one inner loop.
From that single skeleton you get three answers for free: Level Order (each level as its own list), Zigzag (alternate the direction per level), and Right Side View (the last node dequeued on each level).
// BFS skeleton — the level-size snapshot
q.push(root)
while q not empty:
sz = q.size() // nodes on this level
for i in 0..sz:
node = q.pop()
// last i ⇒ right-side view
push node.left, node.right
q.push(root)
while q not empty:
sz = q.size() // nodes on this level
for i in 0..sz:
node = q.pop()
// last i ⇒ right-side view
push node.left, node.right
Time Complexity
O(N)
Every node is enqueued and dequeued exactly once.
Space Complexity
O(W)
Queue holds at most one full level; W is the max width of the tree.
Live Visualization
Dequeued (current)
In queue
Picked for output
Fully processed
Queue (front → back)
Output by level
node = –
level = 0
dir = L→R
visited = 0
Step 0 / 0
Current
–
dequeued node
Queue size
0
nodes waiting
Level
0
current depth
Visited
0
nodes emitted
Pick a mode and hit Play to sweep the tree level by level.
✓ Done
Speed
Step-by-step trace
| # | Action | Node | Level | Queue | Output so far |
|---|
C++ — Level Order (LC 102)