Binary Search Trees

One rule changes everything

The BST invariant (an invariant is a rule that must stay true at all times) says: for every node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger. Not just the immediate children. Every value anywhere below on that side.

That last part trips up beginners. It is not enough for a node's left child to be smaller; the left child's entire subtree must be smaller. A node holding 10 with a left child 5 whose right child is 12 is not a valid BST, because 12 sits in 10's left subtree while being bigger than 10.

Why does the rule matter? Because at any node, one comparison tells you which half of the tree your target could live in. Looking for 7 at a node holding 10? Seven is smaller, so if it exists at all it is in the left subtree. The entire right subtree is eliminated without a glance. That is binary search, running on a tree instead of an array.

Searching: one comparison per level

Searching a BST is a controlled fall from the root. Compare the target with the current node. Equal? Found it. Smaller? Step left. Larger? Step right. Hit null? The value is not in the tree.

Each comparison drops you exactly one level, so the cost of a search equals the height of the tree. In a balanced tree (one where the levels are filled fairly evenly) the height is about log n, giving O(log n) searches. The code is a short loop, no recursion required, though a recursive version is just as natural.

boolean search(TreeNode root, int target) {
    TreeNode current = root;
    while (current != null) {
        if (current.val == target) return true;
        if (target < current.val) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return false;
}

Insertion: search, then attach

Inserting a value reuses the search walk. Follow the same left-or-smaller, right-or-larger steps as if searching for the new value. When you fall off the tree at a null reference, that empty spot is exactly where the value belongs. Attach a new node there and the ordering rule still holds for every ancestor you passed.

A clean way to write this in Java is recursively: insert into the correct subtree and return the possibly-new subtree root, reassigning the child link on the way back up. New values always become leaves; nothing already in the tree ever moves. Like search, insertion costs one comparison per level, so it is O(h), where h is the height.

TreeNode insert(TreeNode node, int val) {
    if (node == null) return new TreeNode(val);
    if (val < node.val) {
        node.left = insert(node.left, val);
    } else if (val > node.val) {
        node.right = insert(node.right, val);
    }
    return node;
}

The free gift: sorted order

Here is an elegant consequence of the invariant. Run an in-order traversal (left subtree, node, right subtree) on a BST and the values come out in ascending sorted order, automatically. At every node, everything smaller is visited first (it all lives on the left), then the node, then everything larger.

Interviewers lean on this constantly. Validate that a tree is a BST? Check that its in-order sequence is strictly increasing. Find the k-th smallest element? In-order traverse and stop at the k-th visit. Any time a BST problem mentions sorted order, rank, or successor, in-order traversal should be your first thought.

The degenerate tree trap

Everything above said O(log n) for a balanced tree, and that qualifier hides a trap. The shape of a BST depends on insertion order. Insert 1, 2, 3, 4, 5 in that order and every new value goes right, producing a chain: a so-called degenerate tree that is really a linked list wearing a tree costume. Its height is n, so search and insert collapse to O(n).

This is why interviewers say BST operations are O(h), not O(log n). The two only match when the tree is balanced. Production libraries solve this with self-balancing trees such as red-black trees (Java's TreeMap and TreeSet use one), which quietly rearrange nodes so the height stays O(log n) no matter the insertion order. You will rarely implement one, but you should know they exist and why.

BSTs keep everything ordered, but many problems only ever ask for one thing: the smallest or largest element right now. Keeping a full BST for that is overkill, a lighter structure called a heap does that one job faster and with far less code, and it is where we head next.

Frequently asked