Data structures problem 22 of 30

Level order traversal

Data structures
Medium

Write level_order(root) that returns the values of a binary tree level by level, from left to right.

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

#     3
#    / \
#   9   20
#      /  \
#     15   7
# level_order(root) -> [[3], [9, 20], [15, 7]]

Show hint

Use a queue (collections.deque). At the start of each level, the queue holds exactly the nodes on that level.

Show solution

from collections import deque

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

This is breadth-first search. Reading len(queue) before the inner loop tells you how many nodes belong to the current level, even though children are being added at the same time. Every node is visited once: O(n). A list with pop(0) would work but is O(n) per pop; deque.popleft is O(1).

Want a problem like this every day? See today's problem and keep a streak going.