Binary Search Tree (BST)

A Binary Search Tree is a regular binary tree with exactly one extra rule applied at every single node, and that one rule is what turns "a tree" into "a structure you can search in O(log n)." This lesson codes insert, search, and delete against that rule, then shows exactly why the O(log n) claim is an average-case claim, not a guarantee.

The BST Invariant

For every node in the tree:

• Every value in its left subtree is less than the node's value.
• Every value in its right subtree is greater than the node's value.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Insert

To insert a value, walk from the root: go left if the new value is smaller, right if it's larger, and when you fall off the tree (hit null), that's where the new node goes.

public static TreeNode insert(TreeNode root, int value) {
    if (root == null) {
        return new TreeNode(value);      // base case: found the empty spot
    }
    if (value < root.val) {
        root.left = insert(root.left, value);
    } else if (value > root.val) {
        root.right = insert(root.right, value);
    }
    // value == root.val: duplicate, no-op (BSTs commonly disallow duplicates)
    return root;
}

Time complexity: O(h) — one comparison per level, where h is the tree's height (O(log n) average, O(n) worst case — see below). Space complexity: O(h) — recursion stack depth equals the path walked.

Search

public static boolean search(TreeNode root, int target) {
    if (root == null) {
        return false;                    // fell off the tree without finding it
    }
    if (target == root.val) {
        return true;
    }
    return target < root.val
        ? search(root.left, target)
        : search(root.right, target);
}

Time complexity: O(h) — at each step exactly one comparison eliminates the entire opposite subtree from consideration, same height bound as insert. Space complexity: O(h) — recursion stack.

Delete

Delete is the trickiest of the three because removing a node with two children would leave a gap — you can't just null it out. The standard approach: find the node's inorder successor (the smallest value in its right subtree — walk left-child pointers as far as possible from root.right), copy that value up into the node being "deleted," and then delete the successor from the right subtree instead (which is guaranteed to be the easy case, since the successor has no left child by definition).

public static TreeNode delete(TreeNode root, int value) {
    if (root == null) {
        return null;                     // value not found, nothing to do
    }

    if (value < root.val) {
        root.left = delete(root.left, value);
    } else if (value > root.val) {
        root.right = delete(root.right, value);
    } else {
        // found the node to delete
        if (root.left == null) {
            return root.right;             // 0 or 1 child (right): promote right child
        }
        if (root.right == null) {
            return root.left;              // 1 child (left): promote left child
        }

        // 2 children: find inorder successor = leftmost node of right subtree
        TreeNode successor = root.right;
        while (successor.left != null) {
            successor = successor.left;
        }
        root.val = successor.val;                       // copy successor's value up
        root.right = delete(root.right, successor.val);  // remove the successor's original node
    }
    return root;
}

Time complexity: O(h) — locating the node is O(h), and locating the successor is bounded by another O(h) walk down the right subtree, so total is still O(h). Space complexity: O(h) — recursion stack.

Average Case O(log n) vs Worst Case O(n)

Every operation above costs O(h), where h is the tree's height. The O(log n) claim you hear about BSTs is really a claim about h — and h is only O(log n) when the tree is reasonably balanced (roughly the same number of nodes on the left and right of every subtree). Nothing in the insert code above enforces that. Insert data in a bad order, and the tree degenerates.

// Inserting already-sorted data, in order, into an empty BST:
TreeNode root = null;
int[] sortedInput = {1, 2, 3, 4, 5, 6};
for (int value : sortedInput) {
    root = insert(root, value);
}

Search, insert, and delete on this degenerate tree all cost O(n) — you've lost every advantage a BST was supposed to give you over a plain array, while paying extra memory for left/right pointers you never use.