Trees · routine

Level by level

Write levels(root) returning a list of lists: the values at depth 0, then depth 1, and so on, each left to right. An empty tree gives [].

Breadth-first search on a tree: a queue, one level at a time.

right answers
arguments left as they should be

Already written for you — you can use these

1class TreeNode:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6 
7def bst(values):
8    """A balanced binary search tree holding the sorted values."""
9    if not values:
10        return None
11    mid = len(values) // 2
12    return TreeNode(values[mid], bst(values[:mid]), bst(values[mid + 1:]))

def levels(root):
    if root is None:
        return []
    return [[root.value]] + levels(root.left) + levels(root.right)

Run adds print(levels(bst([1, 2, 3, 4, 5, 6, 7]))) after your code, to try it.

Stuck on the idea rather than the code? The Building and walking trees lesson walks through it.