Exercise 2 solution

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

    def range_query(n, lo, hi):
        """Values v with lo <= v <= hi, in order, skipping subtrees that cannot match."""
        if n is None:
            return []
        out = []
        if lo < n.value:
            out += range_query(n.left, lo, hi)
        if lo <= n.value <= hi:
            out.append(n.value)
        if n.value < hi:
            out += range_query(n.right, lo, hi)
        return out

    def is_bst(n, low=None, high=None):
        if n is None:
            return True
        if low is not None and n.value <= low:
            return False
        if high is not None and n.value >= high:
            return False
        return is_bst(n.left, low, n.value) and is_bst(n.right, n.value, high)

    good = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
    print(range_query(good, 4, 10))
    print(range_query(good, 20, 30))
    print(range_query(good, 1, 14))
    print(is_bst(good))

    bad = Node(5, Node(3, None, Node(7)), Node(8))
    print(is_bst(bad))
    # Checking only each node against its direct children accepts the bad tree:
    print(all((n.left is None or n.left.value < n.value) and
              (n.right is None or n.right.value > n.value)
              for n in (bad, bad.left, bad.right)))
    print(is_bst(None))

Output:
    [6, 8, 10]
    []
    [1, 3, 6, 8, 10, 14]
    True
    False
    True
    True

range_query only descends left when lo is below the current value and only
descends right when hi is above it, so whole subtrees outside the range are
never visited. The cost is proportional to the height plus the number of
matches, not to the size of the tree.

is_bst passes down the window of values each node is allowed to have. In the
bad tree every parent beats its children (the last check proves it), but 7 sits
in the left side of 5, so a search for 7 starting at the root would go right
and never find it. The window check catches this because 7 must be below 5.
An empty tree counts as a valid search tree.