Binary search tree

Why it costs this much

Each comparison discards one subtree, so a lookup follows a single root-to-leaf path of length at most h.

Code

def search(node, key):
    while node:
        if key == node.key:
            return node
        node = node.left if key < node.key else node.right   # one step per level
    return None    # at most h steps, where h is the tree height

Common pitfalls

Inserting sorted keys into a plain BST builds a chain, so h equals n and every operation is O(n). Balanced trees prevent this.

Operation by operation

Binary search tree search, insert, delete. Average assumes keys inserted in random order. Cost is O(h) for tree height h. Inserting sorted keys makes the tree a chain, and every operation O(n).