Binary search trees

To find a value in the trees of the last step, you may have to look at every node: O(n). The recursion module's sorted binary tree, which interviews call a binary search tree (BST), keeps its values in an order that lets a search skip most of them. At every node:

• every value in the left subtree is smaller than the node's value;
• every value in the right subtree is greater.

(In these lessons, a BST holds each value once.) In the recursion module you searched one, added values to one and printed one in order. This step adds what those operations cost, why the order of the inserts decides the shape of the tree, and how to build a tree that stays balanced.

        8
      /   \
     3     12
    / \      \
   1   6      15

To look for 6, start at the root. 6 is smaller than 8, so it can only be on the left: the whole right subtree is out of the game. 6 is greater than 3, so go right, and there it is. Each comparison moves one level down and drops a whole subtree, as binary search drops half of a sorted list.

Search and insert

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


def contains(node, value):
    while node is not None:
        if value == node.value:
            return True
        if value < node.value:
            node = node.left
        else:
            node = node.right
    return False


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


def smallest(node):
    while node.left is not None:
        node = node.left
    return node.value


root = None
for value in [8, 3, 12, 1, 6, 15]:
    root = insert(root, value)
print(contains(root, 6), contains(root, 7))
print(smallest(root), root.left.right.value)

True False
1 6

contains needs no recursion: a loop walks down until it finds the value or falls off the tree at None. insert walks down in the same way and puts a new node where the search fell off. Unlike the recursion module's add, it returns the root of the tree it was given, so that its caller can store it, and so it works on an empty tree too: for None, the root is the new node itself. A value that's already in the tree isn't added again. The smallest value is as far left as you can go, and the largest as far right.

The classic mistake is to call insert(node.left, value) without the node.left = in front, or insert(root, value) without root =. The new node is made, returned and thrown away, and the tree never grows.

The shape depends on the order

Search, insert, smallest and largest each follow one path down: O(h) for a tree of height h. A balanced tree has a height of about log₂ n, so even a million values need only about 20 steps. But nothing keeps this tree balanced: its shape comes from the order of the inserts. This program builds a tree from the same seven values in two orders, then inserts 2,000 values in sorted order:

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


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


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


for order in [[4, 2, 6, 1, 3, 5, 7], [1, 2, 3, 4, 5, 6, 7]]:
    root = None
    for value in order:
        root = insert(root, value)
    print(order, "height", height(root))

root = None
for value in range(1, 2001):
    root = insert(root, value)

[4, 2, 6, 1, 3, 5, 7] height 3
[1, 2, 3, 4, 5, 6, 7] height 7

Traceback (most recent call last):
  File "main.py", line 32, in <module>
    root = insert(root, value)
  File "main.py", line 14, in insert
    node.right = insert(node.right, value)
                 ~~~~~~^^^^^^^^^^^^^^^^^^^
  File "main.py", line 14, in insert
    node.right = insert(node.right, value)
                 ~~~~~~^^^^^^^^^^^^^^^^^^^
  File "main.py", line 14, in insert
    node.right = insert(node.right, value)
                 ~~~~~~^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

In sorted order, each new value is the greatest so far and goes to the right of everything: the tree becomes a chain, a list in disguise, with h = n. Every search is then O(n), and building the tree costs 1 + 2 + ... + n steps, O(n²). The recursive insert also goes one call deeper for each node, and Python gives up at about 1000 nested calls. A loop version of insert gets rid of the error, but not of the slowness: the chain is still 2,000 levels deep.

Keeping it balanced

When the values come sorted, you can choose the order of the tree yourself. Make the middle value the root: half of the values are smaller and go to its left, half are greater and go to its right. Then build each half in the same way, around its own middle value. The height is about log₂ n, so the recursion stays shallow too. Pass the indexes low and high of the part to build instead of slices, and nothing gets copied: each value becomes one node, O(n) in all.

Java's TreeMap and C++'s std::map are self-balancing trees (red-black trees, usually): they reshape themselves after every insert, so they stay O(log n) whatever the order. Python's standard library has no such tree. For "is it there?" questions, use a set or a dict, and for sorted data, a sorted list with bisect.