Level Order Traversal

Use a queue that starts with the root. At each step, note how many nodes are in the queue, because that is exactly the number of nodes on the current level. Remove that many nodes, record their values, and enqueue their children.

from collections import deque


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


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


tree = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(level_order(tree))

The output is the list 1, then 2 and 3, then 4. The root is alone on the first level, its two children are on the second, and the node with value four is on the third.

The mechanism is the level boundary. The queue holds the not yet processed nodes, and by recording its length before you start popping you know how many belong to this level. The children you enqueue go behind those nodes, so they belong to the next level. The range is evaluated once at the start of the loop, which is exactly why it must be captured rather than recomputed.

The trade-off to name is that this is breadth first traversal, so it uses memory proportional to the width of the tree rather than its depth. For a balanced tree that is half the node count, which is fine, but for a very wide tree it can be large. The depth first traversals use memory proportional to the height instead. The other detail worth stating is that the loop condition is checked against the queue rather than a level count, and the level list is built inside the loop so that the output keeps the level grouping.

A complete binary tree has every level filled except possibly the last, which is filled from the left. The level order traversal then lists the values in a complete, predictable shape.

from collections import deque


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


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


tree = TreeNode(1,
                TreeNode(2, TreeNode(4), TreeNode(5)),
                TreeNode(3, TreeNode(6), TreeNode(7)))
print(level_order(tree))

The output is 1, then 2 and 3, then 4, 5, 6 and 7. The first level holds the root, the second holds its two children, and the third holds the four grandchildren filled from the left.

The mechanism is that the queue processes nodes in the order they were inserted, and insertion follows the level structure. The number of nodes on each level of a complete tree is a power of two up to the last level, so the shape of the output is easy to predict.

The trade-off to name is that level order on a complete tree is the same as reading the tree as if it were a heap, which is why the level order traversal is the natural first step when you want to check whether a binary tree is a valid heap. The other point is that the grouping into levels is what makes it useful for problems that ask about horizontal distance, such as finding the rightmost value at a given depth, and for printing a tree level by level with indentation.

A list that you only ever grow, with a pointer that walks forward through it, behaves exactly like a queue. The level boundary is captured by remembering where the list ends before you start the level.

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


def level_order(root):
    if root is None:
        return []
    queue = [root]
    head = 0
    levels = []
    while head < len(queue):
        level = []
        end = len(queue)
        while head < end:
            node = queue[head]
            head += 1
            level.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels


tree = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(level_order(tree))

The output is 1, then 2 and 3, then 4, which matches the queue based version exactly.

The mechanism is that the head pointer never moves backwards, so each node is visited exactly once, and the list grows to hold every node that has been discovered. The end variable captures the length of the list at the start of the level, which is the number of nodes belonging to that level, because the children appended during the level go beyond that point in the list.

The trade-off to name is that this version never removes anything, so the list holds every node in the tree by the end, which is linear memory in the node count. A deque based queue releases nodes as they are processed, so its peak usage is only the widest level. The list version is still worth knowing because it avoids importing anything and because the same pattern of capturing the end marker is what you use in other breadth first problems where the structure needs to be revisited.