Level order with a deque

The traversals of the last step go deep first: down the left side before anything on the right. Sometimes you want a tree level by level instead: the root, then its children, then their children, each level from left to right. That's level order, also called breadth-first search (BFS).

It needs a queue: first in, first out, like a line at a ticket counter. Put the root in the queue. Then, again and again, take the node at the front, visit it, and put its children at the back. A node's children wait behind every node that is already in line, so the whole level above them goes first.

collections.deque

A list makes a poor queue. queue.pop(0) removes the first item, and every other item moves one place to close the gap: O(n). The collections.deque (said "deck", short for double-ended queue) adds and removes at both of its ends in O(1):

>>> from collections import deque
>>> queue = deque([10, 20])
>>> queue.append(30)
>>> queue.popleft()
10
>>> queue
deque([20, 30])
>>> len(queue)
2

Level by level

Here is level order, and a version that keeps the levels apart. Many questions need to know where one level ends: the widest level, the average of each level, the last node of each level. The trick: at the start of each round of the while loop, the queue holds exactly one whole level. So take len(queue) nodes in a for loop. Those are the level, and the children they add make up the next one:

from collections import deque


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


def level_order(root):
    order = []
    queue = deque()
    if root is not None:
        queue.append(root)
    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)
    return order


def levels(root):
    result = []
    queue = deque()
    if root is not None:
        queue.append(root)
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.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(level)
    return result


#        8
#       / \
#      3   12
#     / \    \
#    1   6    15
root = Node(8, Node(3, Node(1), Node(6)), Node(12, None, Node(15)))
print(level_order(root))
print(levels(root))

[8, 3, 12, 1, 6, 15]
[[8], [3, 12], [1, 6, 15]]

range(len(queue)) is worked out once, when the for loop starts, so the children appended during the round wait for the next round. The last value of each level is what you'd see looking at the tree from its right side: 8, 12 and 15 here.

Only real children go into the queue. Appending a None child would put it in line too, and node.value on it would stop the program with an AttributeError:

from collections import deque


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


queue = deque([Node(8, Node(3))])
while queue:
    node = queue.popleft()
    print(node.value)
    queue.append(node.left)
    queue.append(node.right)

8
3

Traceback (most recent call last):
  File "main.py", line 14, in <module>
    print(node.value)
          ^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'value'

What it costs

Each node goes into the queue once and comes out once, O(1) each with a deque: O(n) time. The memory is the queue, which never holds more than about two levels: O(w), for the widest level w. In a full tree the last level holds half of the nodes, so that can be O(n), while a depth-first traversal needs O(h). With a list and pop(0) you get the same answers, but each pop costs O(n), so a wide tree takes O(n²). And level order uses no recursion at all: a tree 100,000 levels deep is no problem.