Binary Search Trees

The ordering invariant is global

Under a strict unique-key policy, every node v satisfies: all keys reachable throughv.left are less than v.key, and all keys reachable through v.right are greater. Each subtree must satisfy the same rule. Checking only the two immediate children is insufficient: a deep descendant can be on the correct side of its parent but the wrong side of an ancestor.

Choose a duplicate-key policy before writing insert

“Duplicates go somewhere” is not a complete contract. The choice affects bounds, deletion, rank, rotations, and whatsize means. A set normally rejects equality; a map updates the existing value; a multiset commonly keeps a count in the unique-key node.

Interactive: build a BST

This original visualization shows how inserted values descend through comparisons and become leaves. Try sorted input as well as mixed input and compare the resulting heights.

Interactive: narrow bounds, delete safely, validate globally

Search for 65 while tracking inherited bounds, remove a node with two children via its inorder successor, then inspect a tree that passes parent-only checks but violates an ancestor bound.

Search and insertion: preserve the candidate-subtree invariant

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


def search(root, target):
    current = root
    while current is not None:
        if target == current.key:
            return current
        current = current.left if target < current.key else current.right
    return None


def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    # equality is rejected under this set policy
    return root

final class Bst {
static final class Node {
    int key;
    Node left, right;

    Node(int key) { this.key = key; }
}

static Node search(Node root, int target) {
    Node current = root;
    while (current != null) {
        if (target == current.key) return current;
        current = target < current.key ? current.left : current.right;
    }
    return null;
}

static Node insert(Node root, int key) {
    if (root == null) return new Node(key);
    if (key < root.key) {
        root.left = insert(root.left, key);
    } else if (key > root.key) {
        root.right = insert(root.right, key);
    }
    // equality is rejected under this set policy
    return root;
}
}

Recursive code uses O(h) call-stack space. The iterative search uses Θ(1) auxiliary space; iterative insertion can do the same if it retains the parent of the null link. Neither form prevents a height-n recursion failure on a chain.

Deletion has three structural cases

The inorder successor is safe because it is greater than every key in the left subtree and no greater than any other key in the right subtree. As the minimum of the right subtree, it has no left child, so its own removal reduces to an easier case. A predecessor-based implementation is the symmetric alternative.

def delete(root, key):
    if root is None:
        return None

    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left

        successor = root.right
        while successor.left is not None:
            successor = successor.left
        root.key = successor.key
        root.right = delete(root.right, successor.key)

    return root

final class BstDelete {
static final class Node {
    int key;
    Node left, right;
    Node(int key) { this.key = key; }
}

static Node delete(Node root, int key) {
    if (root == null) return null;

    if (key < root.key) {
        root.left = delete(root.left, key);
    } else if (key > root.key) {
        root.right = delete(root.right, key);
    } else {
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;

        Node successor = root.right;
        while (successor.left != null) {
            successor = successor.left;
        }
        root.key = successor.key;
        root.right = delete(root.right, successor.key);
    }

    return root;
}
}

Payload caution: for a key-value node, move/copy the complete record, not the key alone. With parent pointers, subtree sizes, counts, or aggregates, repair every affected field while unwinding. External references to node objects also make “copy key then delete successor” observably different from transplanting the successor node.

Validation requires inherited bounds

Carry the range allowed by all ancestors. A left edge tightens the upper bound to the parent key; a right edge tightens the lower bound. The strict code below matches the reject-duplicates policy. Inclusive endpoints must change if the chosen policy places equals on a side.

def is_valid_bst(root):
    def valid(node, low, high):
        if node is None:
            return True
        if low is not None and node.key <= low:
            return False
        if high is not None and node.key >= high:
            return False
        return (valid(node.left, low, node.key)
                and valid(node.right, node.key, high))

    return valid(root, None, None)

final class BstValidation {
static final class Node {
    int key;
    Node left, right;
    Node(int key) { this.key = key; }
}

static boolean isValidBst(Node root) {
    return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

static boolean valid(Node node, long low, long high) {
    if (node == null) return true;
    if (node.key <= low || node.key >= high) return false;
    return valid(node.left, low, node.key)
        && valid(node.right, node.key, high);
}
}

For arbitrary comparable keys, use optional bound objects rather than numeric sentinels. An alternative validator checks that inorder output is strictly increasing, but it must remember the previous key and apply the same duplicate policy.

Complexity is a function of height

Let height h be the number of edges on the longest root-to-leaf path (empty tree −1, leaf 0). A path operation examines at most h + 1 nodes, so it is O(h), with worst-case Θ(h) when the path reaches the deepest level. A balanced tree has h = Θ(log n); an insertion chain has h = n − 1.

Degeneracy: a BST does not balance itself

Ordered queries are the reason to choose a BST

Language-neutral pseudocode: order-statistic select

# select(node, r): key with zero-based rank r
while node is not null:
    leftSize = size(node.left)
    if r < leftSize:
        node = node.left
    else if r == leftSize:
        return node
    else:
        r = r - leftSize - 1
        node = node.right
return NOT_FOUND
 
# Mutation obligation:
# node.size = 1 + size(node.left) + size(node.right)

Common failure modes