Level Order Traversal
Depth-first traversal follows one branch to the bottom before looking at the next; level order visits everything one row at a time. That difference is entirely down to which structure holds the pending nodes, and swapping a stack for a queue is the whole implementation.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
struct Node {
int val;
Node* left;
Node* right;
};
Node* make(int v) {
Node* n = new Node();
n->val = v; n->left = NULL; n->right = NULL;
return n;
}
int main() {
Node* root = make(1);
root->left = make(2); root->right = make(3);
root->left->left = make(4); root->right->right = make(5);
Node* q[16];
int head = 0, tail = 0;
q[tail++] = root;
while (head < tail) {
int levelSize = tail - head;
for (int i = 0; i < levelSize; i++) {
Node* cur = q[head++];
cout << cur->val << ' ';
if (cur->left != NULL) q[tail++] = cur->left;
if (cur->right != NULL) q[tail++] = cur->right;
}
cout << endl;
}
return 0;
}A fixed array with head and tail indices acts as the queue, so the whole visit order stays on screen instead of being consumed and discarded.
How it works, step by step
The queue enforces the level ordering
A node's children are enqueued behind every node already waiting, all of which are at the same depth or shallower. FIFO therefore guarantees that depth d is fully drained before any node at depth d+1 is dequeued.
levelSize snapshots the current row
Measuring the number of pending nodes before the inner loop captures exactly one level, because the enqueues that follow belong to the next level. Without that snapshot the loop cannot tell where one row ends.
head advances instead of erasing
Dequeuing moves an index forward, which is O(1). Erasing from the front of a container shifts every remaining element and is O(n). Here the nodes simply stay in the array, so the finished traversal order is still there to inspect afterwards.
Null children are filtered at enqueue time
Checking before pushing keeps the queue free of nulls so the dequeue side needs no guard. The alternative — pushing nulls and checking on dequeue — is what you want if you need to print placeholders for missing children.
The loop ends when the queue is drained
head < tail is true exactly while unprocessed nodes remain, since tail marks where the next arrival goes and head marks the next departure. Every node is enqueued once and dequeued once, so the loop runs n times regardless of tree shape.
Complexity
Each node is enqueued and dequeued exactly once; the memory is bounded by the widest level, which for a complete tree is about n/2 — meaning level order can use substantially more memory than a depth-first traversal on wide trees, and much less on deep ones.
Common bugs
Measuring the level length inside the inner loop
tail grows as children are enqueued, so a loop bounded by the live length tail - head never ends the level — it keeps consuming nodes from deeper rows and every level after the first is wrong. Snapshot levelSize before the inner loop starts.
Dequeuing with erase(q.begin())
If you back the queue with a vector and pop by erasing the front, every remaining element shifts on each removal and an O(n) traversal becomes O(n squared). On a wide tree with tens of thousands of nodes that is the difference between instant and visibly slow, for no functional gain.
Enqueueing null children
Pushing cur->left unconditionally puts nulls in the queue, and the next dequeue crashes on cur->val. Either filter on the way in, as here, or check for null immediately after dequeuing — but do one of them consistently, not half of each.
Using a stack and expecting level order
Swapping the queue for a stack silently produces a depth-first order that still visits every node, so the output looks like a valid traversal and is simply the wrong one. If your levels are interleaved, check which end of the container you are removing from.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What is level order traversal of a binary tree?
A breadth-first walk that visits all nodes at depth 0, then all at depth 1, and so on. It is implemented with a queue: dequeue a node, output it, and enqueue its children. This is the traversal you want for printing a tree by rows or finding the shallowest node matching a condition.
How do you separate levels in a level order traversal?
Record the queue's size before processing each level and dequeue exactly that many nodes. Everything enqueued during that inner loop belongs to the next level, so the count cleanly delimits the current row. Reading the size inside the loop instead of before it is the classic bug.
Why does level order traversal use a queue instead of a stack?
Because FIFO ordering guarantees that nodes are processed in the order they were discovered, and nodes at depth d are all discovered before any node at depth d+1. A stack reverses that, processing the most recently discovered node first, which produces a depth-first traversal instead.
What is the space complexity of level order traversal?
O(w), where w is the maximum number of nodes on any single level. For a complete binary tree the bottom level holds roughly half the nodes, so this is O(n) — noticeably worse than the O(h) of a recursive depth-first traversal on a balanced tree, and much better on a deep skewed one.