6.1 BST Properties and Operations

Binary Search Tree Fundamentals

Binary search trees (BSTs) organize data into a node-based hierarchy where every element has a defined position based on its value. This structure lets you find, add, or remove elements quickly by making simple comparisons at each level, rather than scanning through everything.

The key difference between a BST and a plain binary tree is the ordering rule that every node must follow. In a balanced BST, this ordering gives you $O(\log n)$ performance for core operations. But if the tree becomes unbalanced, performance can degrade all the way to $O(n)$.

BST Properties

A valid BST must satisfy all of the following:

• Left subtree rule: Every node in a node's left subtree has a key less than that node's key.
• Right subtree rule: Every node in a node's right subtree has a key greater than that node's key.
• Recursive structure: Both the left and right subtrees must themselves be valid BSTs. This isn't just about immediate children; the property must hold for every descendant.

Each node stores a key (its data), a reference to a left child, and a reference to a right child. Some implementations also include a parent reference to simplify certain operations like deletion.

BSTs vs Regular Binary Trees

Regular binary trees (like heaps or expression trees) impose no ordering relationship between parent and child keys. A heap, for example, enforces a vertical rule (parent ≥ children in a max-heap) but has no left-vs-right ordering.

BSTs enforce the left-less-than, right-greater-than property, which is what makes efficient searching possible. The tradeoff is that regular binary trees can be kept structurally balanced (complete, full, or perfect) by design, while a BST's shape depends entirely on the order elements are inserted. Insert the values 1, 2, 3, 4, 5 in that order, and your BST degenerates into a linked list.

BST Operations and Complexity

Search

Searching a BST follows a straightforward comparison-and-branch pattern:

1. Start at the root node.

2. Compare the search key to the current node's key.

   • If they're equal, you've found it. Done.
   • If the search key is less, move to the left child.
   • If the search key is greater, move to the right child.

3. Repeat step 2. If you reach a null reference (no child where you need to go), the value isn't in the tree.

Each comparison eliminates an entire subtree from consideration. In a balanced tree with 1,000 nodes, you'd make roughly 10 comparisons instead of 1,000.

Insertion

Insertion works almost identically to search. You're looking for the spot where the new value would be if it existed:

1. Starting at the root, compare the new key with the current node's key.
2. If the new key is less, move left. If greater, move right.
3. Repeat until you hit a null reference. That null spot is where the new node belongs.
4. Create a new node and attach it there.

The new node is always inserted as a leaf. This is simple but means the tree's shape depends on insertion order.

Deletion

Deletion is the trickiest operation because removing a node from the middle of the tree requires maintaining the BST property. There are three cases:

• Case 1 (leaf node): Simply remove it. No children to worry about.
• Case 2 (one child): Replace the deleted node with its single child. The BST property is preserved because that child's entire subtree was already on the correct side.
• Case 3 (two children): You can't just remove the node without breaking the tree structure. Instead:
  1. Find the inorder successor, which is the smallest key in the right subtree. (You find it by going right once, then left as far as possible.)
  2. Copy the inorder successor's key into the node you want to delete.
  3. Delete the inorder successor from the right subtree. Since the inorder successor has at most one child (a right child), this reduces to Case 1 or Case 2.

Time Complexity

All three core operations depend on the height of the tree, since you traverse from root toward a leaf.

In a balanced BST, the height is approximately $\log_2 n$, so each step roughly halves the remaining nodes. In the worst case, the tree is completely skewed (every node has only one child), making the height equal to $n$. At that point, the BST offers no advantage over a linked list.

This worst-case behavior is exactly why self-balancing BST variants (AVL trees, red-black trees) exist: they guarantee $O(\log n)$ height regardless of insertion order.