Return the values of a binary tree grouped by depth, top to bottom and left to right within each level.

#      1
#     / \
#    2   3
#         \
#          4
levels(root)  # [[1], [2, 3], [4]]

A queue visits nodes in the order they were discovered, which is level order. To know where one level ends, take the queue's current length before processing, and handle exactly that many nodes.

from collections import deque

queue = deque([root])
node = queue.popleft()

deque.popleft is constant time, while list.pop(0) shifts every remaining item.

Handle the empty tree before you start, or None will end up in the queue.

Using the Node class in the starter, write levels(root) returning a list of lists of values, one inner list per depth. An empty tree (None) gives [].

The explanation opens here once every check passes.