Binary Search Tree

The ordering invariant

For every node, all keys in its left subtree are smaller and all in its right are larger. So searching is like binary search: compare, then go left or right, halving the tree each step — O(h).

Search & insert

Both follow one path from the root; insert drops the new key where the search would have failed.

def search(node, key):
    while node and node.val != key:
        node = node.left if key < node.val else node.right
    return node

def insert(node, key):
    if not node: return Node(key)
    if key < node.val: node.left = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node

In-order = sorted

An in-order traversal of a BST yields keys in ascending order. That's a quick way to validate a BST or find the k-th smallest element.

Quick check: Insert 1,2,3,4,5 in order into an empty unbalanced BST. Search cost becomes...

• O(log n)
• O(n)
• O(1)