Overview
Level-order traversal is a breadth-first search (BFS) over a binary tree: it visits all nodes at depth 0, then all at depth 1, and so on, moving level by level from top to bottom and left to right.
Unlike the depth-first traversals, it is naturally iterative and driven by a queue rather than recursion, making it the go-to method whenever you need results grouped by level or the shortest path in edge count.
How Level-order Traversal works
- Push the root node into an initially empty queue.
- Dequeue the front node and visit (process) it.
- Enqueue its left child then its right child, if they exist.
- Repeat until the queue is empty; nodes come out strictly in level order.
When to use it
- Printing or grouping a tree level by level, e.g. for a pretty-printed diagram.
- Finding the shortest path in edges from the root, or the minimum depth of a node.
- Computing per-level results such as the maximum value on each level or the right-side view.
Complexity analysis
Every node is enqueued and dequeued exactly once, so level-order runs in O(n) time. Its space is O(w), where w is the maximum width of the tree — the largest number of nodes on any single level, which can reach about n/2 near the bottom of a full tree.
Frequently asked questions
Why use a queue instead of a stack for level-order?
A queue is first-in-first-out, so nodes are processed in the order they were discovered — level by level. A stack would reverse that into a depth-first order instead.
How do I know where one level ends and the next begins?
Record the queue's size at the start of each round and dequeue exactly that many nodes; those nodes form one complete level before their children take over.