Binary Search Trees (BST)

Introduction

In our Binary Search post, we saw how fast $O(\log n)$ searching can be on a sorted array. The problem? Inserting a new element into an array takes $O(n)$ time because you have to shift everything to make room.

On the other hand, a Linked List allows $O(1)$ insertions, but searching takes $O(n)$ time because you can’t jump to the middle.

A Binary Search Tree (BST) gives us the best of both worlds. It is a Binary Tree with one strict, unbending rule:

For every node, all values in its left subtree must be strictly smaller than the node’s value. All values in its right subtree must be strictly greater than the node’s value.

The BST Structure

Take a look at the root node (8). Every single number to its left (3, 1, 6, 4, 7) is smaller than 8. Every single number to its right (10, 14, 13) is greater than 8. This rule applies recursively to every node, not just the root.

Because of this property, if we perform an In-order Traversal (Left, Root, Right) on this tree, we get the numbers perfectly sorted: 1, 3, 4, 6, 7, 8, 10, 13, 14.

Core Operations

1. Searching — $O(\log n)$

Searching a BST is incredibly intuitive. It is exactly how you would play a “guess the number” game.

Let’s find the number 7.

1. Start at the root (8). $7 < 8$, so we must go left.
2. We arrive at (3). $7 > 3$, so we must go right.
3. We arrive at (6). $7 > 6$, so we must go right.
4. We arrive at (7). Match found!

We found the node in just 4 steps, completely ignoring the other half of the tree.

public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || root.val == val) return root; // Found it or empty
    
    if (val < root.val) {
        return searchBST(root.left, val);  // Search left
    } else {
        return searchBST(root.right, val); // Search right
    }
}

2. Insertion — $O(\log n)$

Inserting is exactly like searching. We traverse the tree until we hit a null spot where the node should be, and we place it there.

Let’s insert 5: $5 < 8$ (left) $\rightarrow$ $5 > 3$ (right) $\rightarrow$ $5 < 6$ (left). The left child of 6 is currently 4. Wait, $5 > 4$ (right). The right child of 4 is null. Insert 5 there.

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val); // Found the empty spot!
    
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else if (val > root.val) {
        root.right = insertIntoBST(root.right, val);
    }
    // (If val == root.val, we usually ignore as standard BSTs don't hold duplicates)
    
    return root;
}

3. Deletion — $O(\log n)$

Deleting is the hardest operation because we cannot break the BST rules. If we want to delete a Leaf (like 1, 4, or 7), it is easy — just remove it. If the node has one child, we just bypass it (like a Linked List deletion).

But if the node has two children (e.g., deleting root node 8)?

1. We cannot just delete it; the tree would split.
2. We must find a replacement that maintains the sorting rules.
3. The replacement is the in-order successor: the smallest node in the right subtree (which would be 10 in our diagram above).
4. Swap the values, then delete the in-order successor.

The Fatal Flaw of the Standard BST

We said BSTs have $O(\log n)$ time complexity. But there is a catch: that is only true if the tree is balanced.

What happens if we insert already-sorted numbers into a BST in this order: 1, 2, 3, 4, 5?

(1)
  \
  (2)
    \
    (3)
      \
      (4)
        \
        (5)

This is no longer a tree; it has devolved into a glorified Linked List! Searching for 5 will take $O(n)$ time, completely defeating the purpose of the data structure.

The Solution: Self-Balancing Trees

To guarantee $O(\log n)$ performance, we use advanced variations like the AVL Tree or Red-Black Tree. These trees automatically detect when they become lopsided and perform “rotations” to pull themselves back into balance.

In Java, TreeMap and TreeSet are built using Red-Black Trees, guaranteeing $O(\log n)$ performance even in the worst case.

Summary Comparison

Practice Problems

1. Search in a BST – LeetCode #700 — Good warm-up for the traversal logic.
2. Insert into a BST – LeetCode #701 — Direct implementation practice.
3. Validate Binary Search Tree – LeetCode #98 — A classic interview question. Hint: Just checking left < root < right is NOT enough. You must pass down min/max bounds.
4. Lowest Common Ancestor of a BST – LeetCode #235 — Leverage the BST sorting rule to solve this efficiently.

What’s Next?

We just saw how a tree can be strictly ordered horizontally (left is small, right is big). But what if we ordered a tree vertically instead (parent is always bigger than children)? That structure is called a Heap, and it powers Priority Queues.