Trees · warm-up

In-order traversal

Write in_order(root) returning a list of the values: everything in the left subtree, then the node, then everything in the right subtree. For a binary search tree this comes out sorted.

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 in_order(root):
    if root is None:
        return []
    return [root.value] + in_order(root.left) + in_order(root.right)

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

Stuck on the idea rather than the code? The Trees lesson walks through it.