How Level-Order Traversal Works

Level-order traversal reads a tree row by row using a queue instead of a stack. It is breadth-first search on a tree, and the only traversal that shows you the tree's shape as you go.

Output so far

Nothing yet.

Not reached
On the stack
Current
Visited

Speed

Step 1 of 13

Level-order walk over 7 values, 3 levels deep.

Counters

Visited: 0/7
In the queue: 0
Tree height: 3
Nodes: 7

Settings

How many values7

How it was built

Level-order

1queue = [root]
2while queue:
3 node = queue.shift()
4 visit(node)
5 enqueue node.left
6 enqueue node.right

What each walk is for

Walk	What you get	Time	Extra space
In-order	Values in sorted order	O(n)	O(h)
Pre-order	Root before children, for copying a tree	O(n)	O(h)
Post-order	Children before root, for freeing or evaluating	O(n)	O(h)
Level-order	Shallowest nodes first, level by level	O(n)	O(w)
Search	One value, by comparing at each node	O(h)	O(1)

n is the number of values, h the height of the tree and w its widest level. Build the tree from sorted values and h grows all the way to n — that is what balancing prevents.

Complexity

Best	Average	Worst	Extra memory
O(n)	O(n)	O(n)	O(w)

w is the widest level, which for a balanced tree is about n/2 — so unlike the depth-first walks, this one uses more memory on balanced trees than on degenerate ones.

How level-order traversal works

Level-order traversal pushes the root into a queue, then repeatedly takes a node off the front, visits it, and pushes its children onto the back. Because the queue is FIFO, everything at depth d comes out before anything at depth d+1. Swapping that queue for a stack turns the same loop into a depth-first walk — the container is the only difference between the two, which is the cleanest way to see what BFS and DFS really are.

Put the root in a queue.
Take the node at the front and visit it.
Push its left child, then its right child, onto the back of the queue.
Repeat until the queue is empty.
To group output by level, record the queue's length before each round — that is exactly the size of the current level.

Implementation

The same algorithm the visualiser is running, written to be read.

from collections import deque


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

    out, queue = [], deque([root])
    while queue:
        # Snapshot the length first, and each round is exactly one level.
        for _ in range(len(queue)):
            node = queue.popleft()
            out.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return out

When to use it

Use it to find the shallowest node matching something: the first match found is the closest to the root.
Use it to print or render a tree by row, and to compute its width or per-level statistics.
Use it to measure height iteratively, without recursion, by counting rounds.
Avoid it on very wide trees if memory is tight — the queue holds an entire level at once.

Check yourself

If the animation made sense, these should too.

What is the only structural difference between level-order and depth-first traversal?

The container. A FIFO queue yields level order; a LIFO stack yields depth-first. The loop around it - take a node, visit it, push its children - is identical, which is the clearest statement of what BFS and DFS actually are.

Level-order uses more memory on a balanced tree than on a degenerate one. Why?

Its queue holds a whole level, and the widest level of a balanced tree is about half its nodes. A depth-first walk holds one path, so it is the degenerate tree - the long path - that costs it memory.