Binary Search Trees: Fast Lookup Until Your Data Arrives Sorted

Quick Answer

In a BST every left descendant is smaller and every right descendant is larger. That makes search, insert and delete O(log n) on a balanced tree — but O(n) if the input arrives sorted, because the tree becomes a straight line.

One rule defines everything

For every node: everything in the left subtree is smaller, everything in the right subtree is larger. That single invariant gives you the whole structure.

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

def insert(root, v):
    if root is None:
        return Node(v)
    if v < root.val:
        root.left = insert(root.left, v)
    elif v > root.val:
        root.right = insert(root.right, v)
    return root

Note the elif rather than else — equal values are ignored here, which is one valid choice. The alternatives are to keep a count on the node or to allow duplicates on one side consistently. Interviewers sometimes ask, and "I chose to reject duplicates" is a fine answer as long as it is deliberate.

Search halves the problem each step

def search(root, v):
    if root is None or root.val == v:
        return root is not None
    return search(root.left, v) if v < root.val else search(root.right, v)

At each node you discard an entire subtree. With 1,000 nodes that is about 10 comparisons; with a million, about 20. This is the same halving idea as binary search on an array, with the advantage that insertion does not require shifting elements.

Building a tree from [50, 30, 70, 20, 40, 60, 80]:

print(search(r, 40))   # True
print(search(r, 45))   # False

In-order traversal comes out sorted

This is the property that makes a BST worth using over a hash table.

def inorder(root, out=None):
    if out is None: out = []
    if root:
        inorder(root.left, out)
        out.append(root.val)
        inorder(root.right, out)
    return out

print(inorder(r))   # [20, 30, 40, 50, 60, 70, 80]

Left, then node, then right — and because of the ordering rule, that visits values in ascending order. A hash table gives you O(1) lookup but no order at all.

That is the real reason to choose a tree: you get sorted iteration, range queries ("every student scoring between 60 and 80"), and nearest-smaller-value lookups. A hash table can do none of those.

The failure mode: sorted input

Here is the part that matters and is frequently skipped.

def height(n):
    return 0 if not n else 1 + max(height(n.left), height(n.right))

# built from [50, 30, 70, 20, 40, 60, 80]
print(height(r))     # 3

# built from [10, 20, 30, 40]  -- already sorted
print(height(deg))   # 4

Seven values gave height 3. Four sorted values gave height 4 — every insert went right, and the tree is now a linked list with extra pointers. Search is O(n), and all the benefit is gone.

This is not a rare edge case. Inserting records in ID order, or dates in chronological order, produces exactly this. It is also why real systems use self-balancing trees — AVL or red-black — which rotate on insertion to keep the height logarithmic. Java's TreeMap and C++'s std::map are red-black trees for this reason.

Deletion, and the three cases

Deletion is the part that gets asked because it has genuine casework:

• No children — remove it.
• One child — replace the node with that child.
• Two children — replace its value with the in-order successor (the smallest value in the right subtree), then delete that successor, which by definition has at most one child.

The third case is the one to be able to explain. You cannot simply promote a child, because that would break the ordering for the other subtree. The successor is the only value that can sit there and keep every ancestor's invariant intact.

In Python you would rarely implement this in production — sortedcontainers or a plain sorted list handles most real needs. Know it for interviews, and for understanding why a TreeMap behaves the way it does. See binary tree traversal for the traversal orders themselves.

Frequently Asked Questions