Binary search trees

Why a BST

A sorted array gives fast search with binary search, O(log n), but inserting a new value means shifting items, O(n). A hash set gives fast insert and lookup, but no order: it cannot answer "what is the next larger value?" or "list everything between 100 and 200". A binary search tree aims for both: ordered data with search, insert and delete in O(h), where h is the height.

The BST property

For EVERY node: all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger. Note the words "all values in the subtree", not just "the children". In this module a BST has no duplicate values. Real systems either forbid duplicates, keep a count in the node, or send equal values consistently to one side; say which one you choose.

        50
       /  \
     30    70
    /  \   /  \
   20  40 60  80

Search and insert: walk one path

To search, start at the root. If the target is smaller, go left; if larger, go right; if equal, you found it. Each step goes one level down, so search is O(h). Insert walks the same path until it falls off the tree at a None, and puts the new node there.

def search(node, target):
    while node is not None and node.val != target:
        node = node.left if target < node.val else node.right
    return node

def insert(node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node                    # equal: ignore the duplicate

def inorder(node):
    return inorder(node.left) + [node.val] + inorder(node.right) if node else []

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)
print(inorder(root))                                # Output: [20, 30, 40, 50, 60, 70, 80]
print(search(root, 60) is not None, search(root, 65))   # Output: True None

The shape depends on the insert order. Inserting 1, 2, 3, 4, 5 in sorted order gives a chain leaning right, with height n − 1, so every operation becomes O(n). Self-balancing trees (Topic 5) fix this by reshaping the tree after inserts and deletes.

Inorder gives sorted order

Inorder visits the left subtree (all smaller values), then the node, then the right subtree (all larger values). Applied at every node, that prints the values in increasing order. This one fact solves many problems: validating a BST (the inorder list must be strictly increasing), finding the k-th smallest value (stop after k visits), and converting a BST to a sorted list in O(n).

Delete: three cases

1. The node is a leaf: just remove it (return None to its parent).
2. The node has one child: replace the node with that child.
3. The node has two children: find its inorder successor, the smallest value in its right subtree (go right once, then left as far as possible). Copy that value into the node, then delete the successor from the right subtree. The successor has no left child, so that second delete is case 1 or 2.

def delete(node, key):
    if node is None:
        return None
    if key < node.val:
        node.left = delete(node.left, key)
    elif key > node.val:
        node.right = delete(node.right, key)
    else:
        if node.left is None:          # cases 1 and 2
            return node.right
        if node.right is None:         # case 2
            return node.left
        succ = node.right              # case 3: two children
        while succ.left:
            succ = succ.left
        node.val = succ.val
        node.right = delete(node.right, succ.val)
    return node

for key in (20, 30, 50):               # a leaf, one child, two children
    root = delete(root, key)
print(inorder(root), root.val)         # Output: [40, 60, 70, 80] 60

Validating a BST: the classic trap

The common wrong answer checks only that node.left.val < node.val < node.right.val at each node. Look at build([5, 4, 6, None, None, 3, 7]): 3 is the left child of 6, so the local check passes, but 3 sits in the RIGHT subtree of 5 and is smaller than 5. Not a BST.

The fix is to pass down the range each node must fit in. The root may be anything (−∞, +∞). Going left, the upper bound becomes the parent's value; going right, the lower bound becomes the parent's value. Each node is checked once: O(n) time, O(h) space. A second correct method is an inorder walk that checks each value is larger than the previous one.

def is_valid_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if not (low < node.val < high):
        return False
    return is_valid_bst(node.left, low, node.val) and is_valid_bst(node.right, node.val, high)

print(is_valid_bst(build([5, 4, 6, None, None, 3, 7])))   # Output: False

Two more classics

K-th smallest: run an iterative inorder and count; stop at the k-th popped node. It costs O(h + k), not O(n), because you stop early. Building a balanced BST from a sorted array: make the middle value the root, build the left half into the left subtree and the right half into the right subtree. Both halves differ in size by at most one, so the tree is height-balanced. It visits each value once: O(n).

Common mistakes

• Validating with children only. Fix: pass (low, high) bounds down, or check that the inorder list is strictly increasing.
• Using 0 or a big number as the starting bounds; values can be negative or huge. Fix: float("-inf") and float("inf"), or None meaning "no bound".
• Forgetting to return the (possibly new) root from insert and delete, so the parent's link is never updated.
• Assuming O(log n). A plain BST built from sorted input is a chain, O(n) per operation. Say "O(h), which is O(log n) only if balanced".
• Choosing the wrong replacement in delete. Use the inorder successor (smallest on the right) or the predecessor (largest on the left), never an arbitrary child.