Binary Tree Level Order Traversal: BFS, Queues and DFS Orders

There are four standard ways to visit every node of a binary tree, and three of them are the same algorithm with a line moved. Preorder, inorder and postorder all go deep first. Level order is the odd one out: it goes wide, row by row, and it needs a different data structure to do it.

That difference is what makes level order the answer to a whole family of questions — the right side view, zigzag order, level averages, minimum depth — and knowing exactly where it comes from makes all of them short.

The problem it solves

Return the values of a binary tree grouped by depth: the root on its own, then its children left to right, then their children, and so on. For a root 3 with children 9 and 20, where 20 has children 15 and 7, the answer is [[3], [9, 20], [15, 7]].

The depth-first orders cannot produce this directly. They visit 9's entire subtree before touching 20, so nodes of different depths come out interleaved. On the same tree, preorder gives 3, 9, 20, 15, 7 — it happens to look level-like here only because 9 is a leaf. Add children under 9 and they appear before 20.

The intuition

Why a queue. Put the root in a queue. Repeatedly take the node at the front and add its children at the back. Children always join behind every node already waiting, and every node already waiting is at the same depth or one shallower. So the queue is always sorted by depth: all of depth d leave before any of depth d + 1. A stack would do the opposite — the newest child would come out next, and you would be doing depth-first search.

Why len(q) gives one row. Just before you start processing a level, the queue contains exactly that level and nothing else: the previous level has been fully consumed, and none of this level's children have been added yet. So read its length once, and pop exactly that many nodes. Their children pile up behind them and form the next row. The one-line for _ in range(len(q)) is the whole trick, and it works because range evaluates the length before the loop starts.

The DFS alternative. You can also produce levels depth-first, as long as you carry the depth down: when you visit a node at depth d, append its value to row d. Going left before right keeps each row in order. The output is identical; only the memory profile differs, which turns out to matter.

Watch it run

The animation walks the same five-node tree. The strip under the tree is the queue itself. Watch the moment a level starts: the strip holds exactly that level, and as each node leaves, its children join at the far end — behind the row being read, never mixed into it.

The code

Level order both ways, two classic variants that fall straight out of the rows, and the three depth-first orders for contrast:

from collections import deque

class Node:
    def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r

def levels(root):
    out, q, peak = [], deque([root] if root else []), 0
    while q:
        peak = max(peak, len(q))
        row = []
        for _ in range(len(q)):         # freeze the level before its children join
            n = q.popleft()
            row.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        out.append(row)
    return out, peak

def levels_dfs(root):                   # same answer, depth-first, depth carried along
    out = []
    def walk(n, d):
        if n is None:
            return
        if d == len(out):
            out.append([])
        out[d].append(n.val)            # left before right keeps each row in order
        walk(n.left, d + 1)
        walk(n.right, d + 1)
    walk(root, 0)
    return out

tree = Node(3, Node(9), Node(20, Node(15), Node(7)))
print(levels(tree)[0])                  # [[3], [9, 20], [15, 7]]
print(levels_dfs(tree))                 # [[3], [9, 20], [15, 7]]
print([row[-1] for row in levels(tree)[0]])        # [3, 20, 7]
print([row if d % 2 == 0 else row[::-1]            # zigzag
       for d, row in enumerate(levels(tree)[0])])  # [[3], [20, 9], [15, 7]]

pre  = lambda n: [n.val] + pre(n.left) + pre(n.right) if n else []
ino  = lambda n: ino(n.left) + [n.val] + ino(n.right) if n else []
post = lambda n: post(n.left) + post(n.right) + [n.val] if n else []
print(pre(tree), ino(tree), post(tree))
# [3, 9, 20, 15, 7] [9, 3, 15, 20, 7] [9, 15, 7, 20, 3]

The last element of each row is the right side view — what you would see standing to the right of the tree. Reversing every other row is zigzag order. Level averages and the largest value per level are one line each on top of levels; minimum depth is the same loop, stopping at the first leaf.

The three depth-first orders differ only in when the node's own value is written: before its subtrees, between them, or after them. Inorder on a binary search tree comes out sorted, which is why it is the one used to validate a BST.

To check both level-order versions against something that shares no code with them, label every node with its path from the root — 0 for a left turn, 1 for a right turn. A node's depth is the length of its path, and within one depth, sorting the paths as strings puts them left to right:

import random

def levels_by_path(root):               # label each node "0"/"1" per left/right turn
    paths, stack = [], [(root, "")]
    while stack:
        n, path = stack.pop()
        paths.append((len(path), path, n.val))  # depth = number of turns
        if n.left: stack.append((n.left, path + "0"))
        if n.right: stack.append((n.right, path + "1"))
    out = []
    for depth, _, val in sorted(paths):         # same depth: "0..." sorts before "1..."
        if depth == len(out):
            out.append([])
        out[depth].append(val)
    return out

def random_tree(size):
    nodes = [Node(0)]
    while len(nodes) < size:
        n, side = random.choice(nodes), random.choice(("left", "right"))
        if getattr(n, side) is None:
            setattr(n, side, Node(len(nodes)))
            nodes.append(getattr(n, side))
    return nodes[0]

random.seed(12)
ok = True
for _ in range(2000):
    root = random_tree(random.randint(1, 25))
    ok &= levels(root)[0] == levels_dfs(root) == levels_by_path(root)
print(ok)                               # True

Two thousand random trees, from single nodes to lopsided chains, all agreeing. Swapping the two recursive calls in levels_dfs makes the same check print False, so it does catch a wrong row order.

The complexity

Every node enters and leaves the queue once: O(n) time, for both versions. Memory is where they part ways. BFS holds one level at a time, so its peak is the widest level. DFS holds one root-to-leaf path, so its peak is the height. The two extremes make the point:

def perfect(depth, v=0):
    return None if depth == 0 else Node(v, perfect(depth - 1), perfect(depth - 1))

def vine(n):
    root = None
    for v in range(n):
        root = Node(v, root)            # every node has only a left child
    return root

bushy, stick = perfect(10), vine(1023)
print(levels(bushy)[1], len(levels(bushy)[0]))     # 512 10
print(levels(stick)[1], len(levels(stick)[0]))     # 1 1023

Both trees have 1,023 nodes. On the perfect tree the queue peaks at 512 — half the tree is the bottom row — while recursion would never go deeper than 10. On the vine the queue never holds more than one node, while recursion would need 1,023 frames, past Python's default limit of about 1,000.

Where it goes wrong

• Reading len(q) inside the loop condition. A while loop that re-checks the queue's length each time mixes the next level into the current row. Snapshot it once.
• Using a list as the queue. list.pop(0) shifts every element, which makes the traversal quadratic. Use collections.deque.
• An empty tree. Seeding the queue with None crashes on .val. Start from an empty queue when there is no root.
• Assuming BFS is always lighter. For bushy trees it is the heavier one; for deep, narrow trees it is the safer one.

The traversal orders themselves have their own lesson: tree traversals.

How to say it in an interview

"I use a queue, because first-in-first-out keeps nodes sorted by depth. At the start of each level I read the queue's length — that's exactly the nodes on this level — pop that many, and push their children for the next round. It's O(n) time, and memory is the widest level. If the tree is wide and shallow, a DFS that carries the depth uses less memory and gives the same rows."

Then mention one variant — right side view is the usual follow-up — and show it is one line on top of the rows. That tells the interviewer you see level order as a tool, not a single answer.