Exercise 1 solution

    class Node:
        def __init__(self, value, left=None, right=None):
            self.value = value
            self.left = left
            self.right = right

    def from_sorted(items, lo=0, hi=None):
        if hi is None:
            hi = len(items)
        if lo >= hi:
            return None
        mid = (lo + hi) // 2
        return Node(items[mid],
                    from_sorted(items, lo, mid),
                    from_sorted(items, mid + 1, hi))

    def height(n):
        return 0 if n is None else 1 + max(height(n.left), height(n.right))

    def inorder(n):
        return [] if n is None else inorder(n.left) + [n.value] + inorder(n.right)

    for size in (0, 1, 7, 15, 1000):
        items = list(range(size))
        t = from_sorted(items)
        print(size, height(t), inorder(t) == items)
    t = from_sorted([10, 20, 30, 40, 50, 60])
    print(t.value, t.left.value, t.right.value)

Output:
    0 0 True
    1 1 True
    7 3 True
    15 4 True
    1000 10 True
    40 20 60

Taking the middle item as the root and recursing on each half gives a tree
whose two sides never differ in size by more than one, so the height is about
log2(n) (10 levels for 1000 items). Passing lo and hi indexes instead of
slicing avoids copying the list at every level (see Data Structures in
Practice 2). With an even number of items there are two possible middles; this
version takes the upper one, so the left side may hold one more item.