Binary Tree Level Order Traversal
Binary Tree Level Order Traversal is LeetCode 102 (Medium). The level order traversal of binary tree asks you to return its node values level by level, each level as its own list, read left to right.
- The first list holds the root, the second its children, and so on down the tree.
- Within a level the order is left to right, which is the order a queue hands the nodes back.
- An empty tree has no levels, so the answer is an empty list.
The tree holds up to 2000 nodes, so a single traversal that touches each node once is all the problem needs.
- The number of nodes in the tree is in the range [0, 2000].
- -1000 <= Node.val <= 1000
Intuition
BFS binary tree level by level works because a queue hands nodes back in the order they arrived, and children are pushed while their parents are being read, so the queue always holds the rest of the current level followed by the start of the next one. The two groups sit side by side with nothing marking the boundary.
The boundary is the queue's length at the moment the level begins. Whatever is in the queue right then is exactly this level; everything pushed afterwards belongs to the next one. So take that count first, pop exactly that many nodes, and the level separates itself.
Any question phrased per level — level order, zigzag order, the right side view, the average of each row, the largest value per row, minimum depth — wants BFS with a queue rather than DFS. The one move that makes them all work is freezing the queue's size before draining it, because that count is the current level's width.
Approach
Before reading on, run [3, 9, 20, null, null, 15, 7] through a queue by hand and write down what the queue holds just before each level starts. Then say which number tells you where level 1 ends. Aim for O(n) time.
Guard the empty tree, then seed the queue
Return an empty list straight away when root is null. Otherwise put the root in a queue, which is the whole of level 0. Skipping the guard queues None as if it were a node and the first node.val raises an error.
Freeze the queue's size at the top of each level
Before reading anything, record size = len(q). Those nodes are the complete current level, because every node pushed from here on is a child and belongs one level deeper. This single line is what keeps the levels apart.
Pop exactly that many nodes
Loop size times and, for each node popped from the front:
- append its value to this level's list.
- push any non-null children to the back.
The queue grows while you do it, which is fine, since the frozen count stops you from reading into the next level.
Store the level and repeat
Add the finished list to the results and go round again while the queue is non-empty. What is left in the queue is precisely the next level, already in left-to-right order, so the next snapshot works the same way.
Binary Tree Level Order Traversal solution in Python | C++ | Java
Common pitfalls
Letting the loop bound re-read the growing queue
while (!q.isEmpty()) {
List<Integer> level = new ArrayList<>();
for (int i = 0; i < q.size(); i++) {
...
}
}while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
...
}
}q.size() in the condition is re-evaluated every turn, and the queue is growing as children are pushed, so the loop swallows the next level too and the rows run together. Capture the count once before the loop.
Using a list and pop(0) as the queue
q = [root] node = q.pop(0)
q = deque([root]) node = q.popleft()
list.pop(0) shifts every remaining element left, so it costs O(n) per call and turns the traversal into O(n²) on a wide tree. deque.popleft() is O(1).
Not guarding the empty tree
res, q = [], deque([root])
if not root:
return []
res, q = [], deque([root])A null root is queued as though it were a real node, and the first node.val raises an error. The constraints allow a tree of 0 nodes, so this case is tested.
Edge cases
root = nullThe guard returns an empty list before the queue is ever seeded.
One level with one value, [[1]]; the root's children are both null so nothing is pushed.
Each level holds exactly one node, giving n single-value lists.
Complexity
w of the widest level, up to about n/2 in a full tree.Binary Tree Level Order Traversal FAQ
Can level order traversal be done with DFS instead of a queue?
Yes. Recurse carrying the depth, and append each value to res[depth], creating the row the first time that depth is reached. It gives the same answer in O(n), but the recursion stack is the tree's height and the queue version matches how the problem is phrased.
Why does the queue hold at most two levels at once?
While a level is being drained, only its own remaining nodes and the children pushed so far are in the queue. Once the level finishes, the queue holds exactly the next level, so it never spans three.