Interview challenge · medium · binary-tree, bfs, queue

Binary Tree Level Order Traversal

The challenge

Given the root of a binary tree, return the values of its nodes level by level: first the root, then its children from left to right, then their children, and so on.

Example

    3
   / \
  9  20         ->  [[3], [9, 20], [15, 7]]
    /  \
   15   7

empty tree      ->  []

Idea: breadth-first search with a queue. At the start of each round, the queue holds exactly one level: take that many nodes out, record their values and push their children, which form the next level. Time O(n), and the queue holds at most one level at a time.

The solution

1# Level Order Traversal - ayotl.dev
2from collections import deque
3
4
5class Node:
6    def __init__(self, v, l=None, r=None):
7        self.v, self.l, self.r = v, l, r
8
9
10def levels(root):
11    out = []
12    q = deque([root] if root else [])
13    # one queue pass per level
14    while q:
15        row = []
16        for _ in range(len(q)):
17            n = q.popleft()
18            row.append(n.v)
19            for c in (n.l, n.r):
20                if c:
21                    q.append(c)
22        out.append(row)
23    return out
24
25
26t = Node(3, Node(9),
27         Node(20, Node(15), Node(7)))
28print(levels(t))
29print(levels(None))

$ python3 binary_tree_level_order_traversal.py

[[3], [9, 20], [15, 7]]

[]

The video

Watch on YouTube →