Binary Search Trees (BST)

A Binary Search Tree (BST) is a binary tree with a special ordering property: for every node, all values in its left subtree are strictly smaller, and all values in its right subtree are strictly larger. This invariant applies recursively at every level—it must hold not just between a parent and its direct children, but throughout every subtree. When the tree is reasonably balanced, this structure enables search, insertion, and deletion in O(log n) time.

Consider a BST like a sorted phone book: to find a name, you open to the middle, decide whether your target comes before or after that page, and jump to the relevant half—skipping the other half entirely. Each comparison eliminates a large portion of the remaining candidates.

The BST Property#

The BST invariant states that:

• All nodes in the left subtree have values less than the current node
• All nodes in the right subtree have values greater than the current node
• Both subtrees must also be valid BSTs

In the invalid tree above, node 60 appears in the left subtree of 50. Even though 60 is locally valid relative to its direct parent 30 (since 60 > 30), it violates the BST property with respect to ancestor 50 (since 60 > 50). This illustrates a critical point: the BST invariant must hold globally against all ancestors, not just the immediate parent.

BST Operations#

Search Operation#

Searching in a BST works by comparing the target against the current node and descending into exactly one subtree—entirely ignoring the other. In a balanced BST, this eliminates roughly half of the remaining candidates at each step, producing O(log n) performance. If the tree is skewed, fewer nodes are eliminated per step, and in the worst case (a fully right- or left-leaning chain), search degrades to O(n).

Insert Operation#

Inserting a new value involves searching for the correct position (the location where a search would fail) and attaching the new node there.

Delete Operation#

Deletion is the most complex BST operation because simply removing a node can break the tree's connectivity. The approach depends on how many children the node has, giving rise to three distinct cases:

Cases 1 and 2 are straightforward: remove the node and rewire the parent's pointer to the surviving child (or to null if there is none). Case 3 is the tricky one: when both children exist, you cannot simply remove the node without disconnecting two subtrees.

The standard solution is to find the node's inorder successor—the smallest value in its right subtree (the leftmost node there)—copy that value into the current node, then delete the successor from the right subtree. This works because:

• The successor is larger than everything in the left subtree (it came from the right subtree).
• The successor is the smallest node in the right subtree, so it is smaller than everything else that remains there.
• The successor has at most one child (a right child), so deleting it reduces to Case 1 or Case 2.

Find Min and Max#

Finding the minimum and maximum values in a BST follows directly from the ordering property. Since every value smaller than a node lies in its left subtree, the overall minimum is always the leftmost node in the tree—you simply follow left child pointers until there are none. Symmetrically, the maximum is always the rightmost node. There is no need to scan the entire tree; you reach the answer in O(h) steps, where h is the tree's height.

Inorder Successor and Predecessor#

The inorder successor of a node is the next node in sorted (inorder) order—the smallest value in the tree that is strictly greater than the target. The inorder predecessor is the previous node in sorted order—the largest value strictly less than the target.

Finding the successor depends on the node's position in the tree:

• If the node has a right subtree: the successor is the leftmost (minimum) node in that subtree.
• If the node has no right subtree: the successor is the nearest ancestor from which you last turned left—the lowest ancestor for which the target node lies in its left subtree. This case requires traversing upward, which in turn requires parent pointers.

The iterative algorithm below handles both cases using a single top-down pass from the root, keeping track of the last ancestor where we went left.

BST Validation#

A common task—and a classic interview question—is to verify whether a given binary tree is a valid BST. The challenge is that checking each node only against its direct children is not sufficient. A value can be locally correct relative to its parent while still violating the BST property relative to a higher ancestor (as the invalid tree diagram above demonstrates with node 60).

The correct approach propagates valid value ranges down the tree during recursion. Each node inherits a lower bound and an upper bound from its ancestors, and its value must fall strictly within those bounds. Any violation at any depth immediately disqualifies the tree.

Build BST from Sorted Array#

Given a sorted array, we can construct a height-balanced BST by recursively picking the middle element as the root at each level. This works because placing the median at the root splits the remaining elements as evenly as possible between the left and right subtrees, minimizing the overall height. A balanced BST of n nodes has height O(log n), which is what keeps all operations efficient. Inserting from the front instead would produce a right-skewed chain of height n.

Complexity Analysis#

When BST Performance Degrades#

Inserting data in sorted (or reverse-sorted) order into a plain BST causes it to degenerate into a linked list. Every new node is always appended at the rightmost (or leftmost) position, and the resulting tree has height n instead of log n. Operations that should take O(log n) on a balanced tree now take O(n)—a dramatic difference for large datasets.

Applications of BST#

Reviewing AI-Generated Code#

BST code is deceptively tricky: the invariant must hold globally across the entire tree, not just locally at each node. AI-generated BST code often looks correct at a glance but contains subtle bugs in validation logic (checking only the direct parent instead of all ancestors) and deletion logic (copying the successor's value without then removing the successor node). Knowing these failure patterns lets you spot errors quickly.

Questions to Ask When Reviewing BST Code#

1. "Does this validate against all ancestors?" — BST validation must propagate min/max bounds down the tree, not just compare a node against its immediate parent.
2. "What does the tree look like after deleting a node with two children?" — Confirm that the successor's value is copied into the deleted node and that the successor is then removed from the right subtree.
3. "What happens if I insert already-sorted values?" — The tree should degrade to a linked list. If the code behaves differently, verify whether a hidden balancing mechanism is present.
4. "How does it handle duplicates?" — There should be a clear, consistently applied policy: ignore them, place them left, or place them right.

Summary#

BSTs provide O(log n) average performance when the tree remains reasonably balanced, but degrade to O(n) when insertion patterns produce a skewed tree—such as inserting already-sorted data. For workloads where input order is unpredictable, a plain BST is often sufficient. When O(log n) must be guaranteed regardless of input, self-balancing trees are required. Continue to AVL Trees to see how rotations automatically restore balance after every insertion and deletion.