Binary Tree Level Order Traversal

Table of Contents +

A tree is just nodes connected by branches. Picture a family tree drawn upside down. The top node is the root. So when an interviewer asks for “level order traversal”, they want you to read the tree row by row. First the root. Then everyone one step below it. Then the next row. And here is the real test. They don’t just want a flat list of numbers. They want each row grouped on its own. So the interviewer is checking two things. Can you walk a tree wide instead of deep? And can you tell where one level ends and the next one starts?

🌳 The Problem

You are given the root of a binary tree. A binary tree is a tree where every node has at most two children, a left one and a right one. You must return the values level by level. The root sits at level zero. Its children sit at level one. And so on down the tree. Each level must come back as its own group inside one big list.

Input tree:
        3
       / \
      9   20
         /  \
        15   7

Output: [[3], [9, 20], [15, 7]]

See how the root 3 sits alone in the first group? Then 9 and 20 form the second group. Then 15 and 7 form the last one. That grouping is the whole challenge.

🤔 The Simple Idea First

Your first thought might be simple. Just do a normal traversal and store the values. But a plain traversal gives you one flat list. It does not tell you when a level ends. So [3, 9, 20, 15, 7] is not enough. You would still have to figure out which number belongs to which level afterwards. And that needs extra bookkeeping, like storing a depth next to every value. It works, but it feels clumsy and it is easy to get wrong.

There is a cleaner way. We read the tree using BFS, which stands for breadth first search. Breadth first means we explore the tree wide before going deep. We finish a whole row before touching the next one. To do this we use a queue.

A queue is a line of people waiting their turn. The first one in is the first one out. We push the root in. Then we keep pulling a node out from the front, and we push its children to the back. That naturally reads the tree row by row.

💡 The Level-Size Trick

Here is the one idea that makes this clean. At the start of each level, we look at how many nodes are sitting in the queue right now. That count is exactly the number of nodes on the current level. Why? Because the queue holds the whole current row and nothing else yet. The next row gets added only while we process this row.

So we record that size first. Then we pull out exactly that many nodes. We collect their values into one group, and we push their children for the next round. When we have pulled out that many, the level is done. We close the group and start fresh for the next level.

That recorded count is the level size. It is the marker that tells us where one level ends and the next begins.

🪜 Steps to Solve

If the root is empty, return an empty list. There is nothing to read.
Put the root into a queue.
While the queue is not empty, record its current size as the level size.
Loop exactly level-size times. Each time, pull a node from the front, add its value to the current level’s group, and push its left and right children to the back if they exist.
After the loop, add the finished group to the answer.
When the queue is empty, return the answer.

💻 The Code

We build a small tree, then run BFS and print each level on its own line so the grouping is easy to see.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

from collections import deque

# A tree node holds a value and two child pointers.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def level_order(root):
    result = []
    if root is None:
        return result

    queue = deque([root])

    while queue:
        level_size = len(queue)      # nodes on this level
        level = []
        for _ in range(level_size):
            node = queue.popleft()   # pull from front
            level.append(node.val)
            if node.left:            # push children
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

if __name__ == "__main__":
    root = Node(3)
    root.left = Node(9)
    root.right = Node(20)
    root.right.left = Node(15)
    root.right.right = Node(7)

    for level in level_order(root):
        print(" ".join(str(v) for v in level))

The output of the above code will be:

3
9 20
15 7

⏱️ Time and Space Complexity

Let n be the number of nodes in the tree.

Approach	Time	Space
Flat traversal with stored depth	O(n)	O(n)
BFS with the level-size trick	O(n)	O(n)

Both touch every node once, so time is O(n). For space, the queue holds at most one full level at a time. The widest level of a tree can hold close to half the nodes. So space is O(n) in the worst case.

Tip

In an interview, say the level-size line out loud. “I record the queue size before the level starts, because that is exactly how many nodes sit on this level.” That one sentence shows you understand why the trick works, not just that it works.

🧩 Key Takeaways

✅ Level order traversal reads a tree row by row, and you return each row as its own group.
✅ BFS with a queue is the natural fit, because a queue pulls nodes in the same order you push them.
✅ The level-size trick is the key. Record the queue size at the start of each level, then process exactly that many nodes.
✅ Both time and space are O(n), since you visit every node once and the queue can hold up to one full level.
✅ Always handle the empty tree first, so you return an empty list instead of crashing.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Previous Validate a Binary Search Tree Next Number of Islands

Share & Connect

Share on LinkedIn