Level Order Traversal (BFS)

Table of Contents +

Say you want to read a tree from the top down, one row at a time. You read the top node first. Then the row below it. Then the row below that. The other traversals (inorder, preorder, postorder) go deep first. They run all the way down one branch before they come back. So they do not give you that neat row-by-row order. Level order traversal does. It visits the tree one level at a time, from the top down. Inside each level it goes left to right.

🌳 What Is Level Order Traversal?

Level order traversal means you visit nodes level by level. You start at the root. That is level 0. Then you visit everything at level 1. Then everything at level 2. And so on, until the tree is done.

Think of a building. You read the names on floor 1 first. All of them, left to right. Then you go up to floor 2 and read those. You never jump to floor 3 while floor 2 still has people you have not greeted. That floor-by-floor sweep is exactly what level order does.

This traversal has another name you will hear a lot: breadth-first search, or BFS. “Breadth-first” just means wide before deep. You finish the full width of one level before you drop down to the next one.

Look at this small tree:

Reading it level by level gives you: 1, then 2 3, then 4 5 6 7. So the level order output is 1 2 3 4 5 6 7.

🎯 Why We Use a Queue

Here is the pain. To go level by level, you have to remember the children you saw but did not visit yet. And you must visit them in the same order you found them, oldest first. If you forget the order, the output gets jumbled.

A queue solves this perfectly. A queue is a line, like people waiting at a billing counter. The first one in is the first one out. We call that FIFO, first in first out. The front leaves first. New people join at the back.

So the trick is simple:

Put the root in the queue.
Take the node at the front and print its value.
Add that node’s children to the back of the queue.
Repeat until the queue is empty.

Because children always go to the back, a whole level finishes before the next level starts. The queue keeps the order honest for you.

Tip

Inorder, preorder, and postorder use a stack (or recursion, which is just a hidden stack). Level order is the odd one out. It uses a queue. Stack means deep-first. Queue means wide-first.

🪜 Steps to Do Level Order Traversal

Let us walk the steps once before we touch code. Say the queue and the tree look like the picture above.

If the tree is empty (root is null), there is nothing to do. Stop.
Add the root node to the back of the queue.
While the queue is not empty, do the next steps.
Remove the node at the front of the queue. Call it current.
Print current’s value.
If current has a left child, add it to the back of the queue.
If current has a right child, add it to the back of the queue.
Go back to step 3.

Let us dry-run it on the sample tree. Watch how the queue grows and shrinks:

Step	Front node taken	Children added	Queue after	Output so far
Start	-	1	1	(empty)
1	1	2, 3	2, 3	1
2	2	4, 5	3, 4, 5	1 2
3	3	6, 7	4, 5, 6, 7	1 2 3
4	4	none	5, 6, 7	1 2 3 4
5	5	none	6, 7	1 2 3 4 5
6	6	none	7	1 2 3 4 5 6
7	7	none	(empty)	1 2 3 4 5 6 7

See how the queue is empty at the end? That is your signal to stop. And the output came out exactly level by level.

💻 Level Order Traversal in Code

Now let us build it. We make the same sample tree by hand. Then we run level order on it with a queue. The code prints the values in level order, just like the dry-run.

[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 links to two children.
class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None

# Visit the tree level by level using a queue.
def level_order(root):
    if root is None:                 # empty tree, nothing to print
        return

    queue = deque()                  # deque works as a fast FIFO queue
    queue.append(root)               # add the root first

    while queue:                     # while the queue is not empty
        current = queue.popleft()    # take the front node out
        print(current.data, end=" ") # print its value

        if current.left:             # add left child to the back
            queue.append(current.left)
        if current.right:            # add right child to the back
            queue.append(current.right)

# Build the sample tree by hand.
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print("Level order: ", end="")
level_order(root)
print()

The output of the above code will be:

Level order: 1 2 3 4 5 6 7

Note

Notice the shape of the loop is the same in every language. Add root, then loop: take from front, print, push children to back. Only the queue tool changes. C uses a plain array with two markers, C++ uses queue, Java uses LinkedList, Python uses deque, and JavaScript uses an array with shift and push.

⏱️ Time and Space Complexity

Let us count the work. Each node enters the queue once and leaves once. We print it once. So if the tree has n nodes, we do work proportional to n. That is O(n) time. Nothing is repeated.

For space, the queue holds the nodes waiting to be visited. In the worst case, that is the widest level of the tree. The bottom level of a full tree can hold about half of all the nodes. So the queue can grow to about n/2, which we still call O(n) space.

Tip

The space is driven by the widest level, not the height. A wide bushy tree needs a big queue. A thin tree that is mostly one long branch needs a tiny queue, because each level has very few nodes.

Here is the summary in one place:

Measure	Complexity	Why
Time	O(n)	Every node is added, removed, and printed exactly once.
Space	O(n)	The queue can hold the widest level, up to about half the nodes.

⚠️ Common Mistakes

A few small slips trip up most beginners. Watch for these:

Using a stack instead of a queue. A stack gives you depth-first order, not level by level. For BFS you need a queue.
Forgetting to check for an empty tree. If the root is null and you skip the check, the code may crash when it tries to read children.
Adding children in the wrong order. Add left first, then right, so each level prints left to right.
Adding a node to the queue but never removing it. Always take the front out before you look at its children, or the loop never ends.

🧩 What You’ve Learned

✅ Level order traversal visits a tree level by level, top to bottom, and left to right inside each level.
✅ It is the same thing as breadth-first search, or BFS, which means wide before deep.
✅ The work is done by a queue, which is first in first out, so children added to the back are visited in the right order.
✅ The steps are simple: add the root, then loop, taking the front node, printing it, and adding its children to the back.
✅ Level order runs in O(n) time and uses O(n) space for the queue in the worst case.

Check Your Knowledge

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

🚀 What’s Next?

Tree Traversals
Height of a Tree

Previous Tree Traversals (Inorder, Preorder, Postorder) Next Height of a Tree

Share & Connect

Share on LinkedIn