DSA Level-Order Traversal

Level-order traversal visits a tree one level at a time, from the top level down. A level is the set of all nodes at the same depth.

The queue does the work

The walk is breadth-first, which means it spreads across a level before going deeper. Parents leave the queue before their children because they joined it earlier.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

from collections import deque


tree = TreeNode(5, TreeNode(2), TreeNode(8))
queue = deque([tree])
order = []
while queue:
    node = queue.popleft()
    order.append(node.value)
    if node.left is not None:
        queue.append(node.left)
    if node.right is not None:
        queue.append(node.right)
print("Order:", order)

One level at a time

The queue length at the start of a round is exactly the size of the current level. Popping that many nodes collects one whole level.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

from collections import deque


def levels(root):
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result


tree = TreeNode(5,
                TreeNode(2, TreeNode(1), TreeNode(3)),
                TreeNode(8))
print("Levels:", levels(tree))

Example

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

from collections import deque


def levels(root):
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result


tree = TreeNode(5,
                TreeNode(2, TreeNode(1), TreeNode(3)),
                TreeNode(8, None, TreeNode(9)))

rows = levels(tree)
total = 0
for depth, row in enumerate(rows):
    print(f"Level {depth}: {row}")
    total += len(row)
print("Nodes visited:", total)

Key points

Level order is the breadth-first walk of a tree, wide before deep
Use a queue for the frontier, the nodes still waiting to be visited
Reading the queue size before a level starts marks where that level ends
Level order visits every node once, so the walk takes one step per node

In this example, the queue starts with only the root 5. Each round pops exactly the nodes of one level and queues their children behind them. The first round prints level 0, the second prints 2 and 8, and the third prints 1, 3 and 9. The rounds visit six nodes in total, which is every node in the tree. Breadth-first search on graphs uses this same queue walk in the graphs entry.

Note

collections.deque pops from the left in one step, while list.pop(0) shifts every remaining item

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

from collections import deque


def levels(root):
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result


tree = TreeNode(5,
                TreeNode(2, TreeNode(1), TreeNode(3)),
                TreeNode(8, None, TreeNode(9)))

rows = levels(tree)
total = 0
for depth, row in enumerate(rows):
    print(f"Level {depth}: {row}")
    total += len(row)
print("Nodes visited:", total)

Exercise

In the closing example, which value does the level-order walk visit last?

5 8 3 9