Trees & Binary Search Trees

A binary search tree (BST) keeps values sorted as you add them. Every node has at most two children. The rule is simple: smaller values go to the left, larger values go to the right. Because the tree is sorted, finding a value means walking down a single path instead of scanning everything.

The idea

A BST stores values so that, at every node, the whole left subtree is smaller and the whole right subtree is larger. That one invariant is what makes it fast.

To insert a value, start at the root and compare. If the new value is smaller, go left; if larger, go right. Repeat until you reach an empty spot, and drop the value there.

To search, do the exact same walk. At each node you either found your value, or you know which half to throw away. Half the tree disappears with every comparison.

This is binary search, but on a tree instead of a sorted array. On a balanced tree the height is about log n, so each lookup touches only about log n nodes.

Walk through it

Press Play on the right, or step with Next / Back. Two phases:

• Insert [8, 3, 10, 1, 6, 14]. Each new value fades in. 8 becomes the root. 3 is smaller, so it goes left. 10 is larger, so it goes right. 1 and 6 settle under 3; 14 settles under 10.
• Search for 6. Start at the root: 6 < 8, go left to 3. Then 6 > 3, go right to 6. That node matches — found. It turns green. Notice the search only ever touched three nodes.

The code panel highlights the matching line: the if key < root.val branch when we go left, the else branch when we go right.

The code, line by line

def insert(root, key):
    if root is None:
        return Node(key)         # empty spot — put it here
    if key < root.val:
        root.left = insert(root.left, key)   # smaller -> left
    else:
        root.right = insert(root.right, key) # larger -> right
    return root
 
def search(root, key):
    if root is None:
        return None              # ran off the tree — not found
    if key == root.val:
        return root              # match!
    if key < root.val:
        return search(root.left, key)   # smaller -> go left
    else:
        return search(root.right, key)  # larger  -> go right

• Both functions are recursive: they call themselves on the left or right child.
• insert stops when it hits an empty spot (root is None) and creates the new node there.
• search stops in two ways: it finds the value (key == root.val), or it runs off the bottom of the tree (root is None) and returns None.
• The comparison (key < root.val) is the same in both — that shared rule is why a BST stays searchable.

Complexity

Each step throws away one subtree, so on a balanced tree you only visit about log n nodes. But a BST can become unbalanced: insert values already in sorted order (1, 2, 3, 4, …) and every node only gets a right child — the tree degrades into a linked list, and search becomes O(n). The space O(h) is the recursion depth, which equals the tree height h.

When to use / pitfalls

Practice