LeetCode 107 · Queue · BFS

Level Order Traversal II, explained with a picture

Generations listed youngest first.

Queue · BFS
▶ Watch it step by step

The problem

Return a tree’s values level by level, but from the bottom level up.

Input:  [3, 9, 20, null, null, 15, 7]
Output: [[15, 7], [9, 20], [3]]

Picture it

Picture listing a family by generation, youngest first. Do a normal level-by-level walk, then reverse the list of rows.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

BFS by level, then reverse. O(n).

Python solution

def level_order(root):
    if not root:
        return []
    q, out = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out[::-1]

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.