Lesson 9 · Non-linear structures

Binary Search Trees

Binary Search Trees impose an ordering constraint on nodes, ensuring that left children are smaller and right children are larger than their parents.

The Invariant

A binary search tree is a binary tree in which, for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. That single rule is the entire structure, and every operation is a consequence of it.

The precision that matters: the rule applies to entire subtrees, not merely to a node's two children. A tree where each node individually beats its children can still violate the invariant — a value deep in the left subtree may exceed the root, which breaks search even though every local comparison looks correct. This is the standard 'validate a BST' interview question, and checking only parent against child is the standard wrong answer.

Validating properly means carrying bounds down the recursion. Every node must lie within a range determined by its ancestors: descending left tightens the upper bound to the parent's key, descending right raises the lower bound. The root starts with infinite bounds on both sides.

Duplicates need an explicit decision, since the invariant as stated has no place for them. The options are to forbid them, to send equals consistently to one side, or to store a count in each node. The last is usually best, since it keeps the tree smaller and the invariant strict. Whichever you pick, the choice must be applied uniformly across search, insert and delete, or the tree becomes inconsistent.

What the invariant buys is direction. At any node, comparing the target against the key tells you which subtree can possibly contain it — and the other subtree is eliminated entirely, without being examined. That is the same halving that makes binary search fast, and it is why the structure carries the name.

Left subtree entirely smaller, right subtree entirely larger
The rule covers subtrees — checking children alone is insufficient
Validate by passing min and max bounds down the recursion
Decide a duplicate policy and apply it to every operation

Search and Insertion

Search starts at the root and compares. Equal means found. Smaller means descend left; larger means descend right. Reaching null means the key is absent. Each comparison discards one subtree, so the work is one root-to-leaf path — O(h).

Insertion performs the identical search. Since the key is not present, the search necessarily ends at a null child position, and that is exactly where the new node belongs — attach it there as a leaf. Insertion never rearranges existing nodes in an unbalanced BST, which is what makes it simple and also what makes it vulnerable to degeneration.

Both are naturally written either recursively or iteratively. The iterative form uses O(1) space rather than O(h) stack frames, which matters on deep trees; the recursive form is shorter and is what most implementations use.

Two further operations follow the same descent. Minimum is found by following left children until one is null; maximum by following right. Both are O(h) and both are needed by deletion.

The cost being O(h) rather than O(log n) is the honest statement, and the distinction is the whole subject of the last section. On a balanced tree h is log n; on a degenerate one it is n.

Compare and descend — each step eliminates one subtree
Insertion ends where the search failed, attaching a new leaf
Iterative versions use O(1) space instead of O(h) frames
Minimum is leftmost, maximum is rightmost

Deletion and Its Three Cases

Deletion is the only genuinely intricate BST operation, because removing a node must leave the invariant intact for everything beneath it. Three cases cover it.

A leaf — no children. Simply remove it and set the parent's pointer to null. Nothing below depends on it.

One child — the node's subtree is entirely on one side. Replace the node with that child, splicing it into the parent's link. Everything in that subtree already satisfies the invariant relative to the parent, so no further work is needed.

Two children — the difficult case, because there is no single child to promote. The node cannot simply be removed; it must be replaced by a value that preserves the ordering, and exactly two values qualify: the inorder successor (the smallest key in the right subtree) or the inorder predecessor (the largest in the left).

Taking the successor: find the minimum of the right subtree by descending left from the right child, copy its key into the node being deleted, then delete that successor node from the right subtree. The recursive deletion is guaranteed to be easy, because the minimum of a subtree has no left child — so it falls into the leaf or one-child case and cannot recurse further.

That termination guarantee is worth stating explicitly in an answer; it is what stops the two-child case from being circular. The predecessor works symmetrically, and alternating between the two is one cheap way to reduce the imbalance that repeated deletions otherwise introduce.

All three cases are O(h): the search to find the node, plus at most one more descent to find the successor.

The three deletion cases
Case	Action	Note
Leaf	Remove it	Set the parent's pointer to null
One child	Promote the child	The subtree already satisfies the invariant
Two children	Copy the inorder successor, then delete it	The successor has no left child — recursion terminates

Leaf: remove. One child: promote it
Two children: replace with the inorder successor or predecessor
The successor is the leftmost node of the right subtree
It has no left child, so the recursive delete cannot recurse again

Key reference

Terms, operations, and practical uses

BST Fundamentals

BST InvariantThe rule that for any node, all values in the left subtree are smaller, and all values in the right subtree are larger.
Search OperationsFinding a value by comparing it to the current node and moving left if smaller, or right if larger, in O(log N) average time.
Inorder PredecessorThe node with the largest value in the left subtree; it is the value immediately preceding the current node in sorted order.

Tree Modification

InsertionTraversing down the tree until a null leaf pointer is reached, and attaching the new node there.
Deletion (No Children)Simply removing the node by setting its parent's pointer to null.
Deletion (Two Children)Replacing the node's value with its inorder predecessor (or successor) and then deleting that leaf node.

Performance Constraints

Balanced CaseWhen the tree is relatively symmetrical, yielding a height of log(N) and allowing optimal operations.
Degenerate CaseWhen elements are inserted in sorted order, the BST becomes a linked list with O(N) operations.
Self-BalancingAdvanced BST implementations that automatically rotate nodes to prevent the degenerate case (e.g., AVL, Red-Black).

Implementation

Search a binary search tree

class BST:
    def __init__(self):
        self.root = None
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        node = self.root
        while True:
            if val < node.val:
                if not node.left:
                    node.left = TreeNode(val)
                    return
                node = node.left
            else:
                if not node.right:
                    node.right = TreeNode(val)
                    return
                node = node.right
    def search(self, val):
        node, steps = self.root, 0
        while node:
            steps += 1
            if val == node.val:
                return steps
            node = node.left if val < node.val else node.right
        return None

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

tree = BST()
for value in (8, 3, 10, 1, 6, 9, 14):
    tree.insert(value)
print('Found 6 in', tree.search(6), 'comparisons')

#include <iostream>
using namespace std;
struct BSTNode {
    int val;
    BSTNode *left = nullptr, *right = nullptr;
    explicit BSTNode(int x) : val(x) {
    }
};
class BST {
    BSTNode* root = nullptr;
    public:
    void insert(int val) {
        BSTNode** link = &root;
        while (*link) link = val < (*link)->val ? &(*link)->left : &(*link)->right;
        *link = new BSTNode(val);
    }
    int search(int val) const {
        BSTNode* node = root;
        int steps = 0;
        while (node) {
            ++steps;
            if (val == node->val) return steps;
            node = val < node->val ? node->left : node->right;
        }
        return -1;
    }
};
int main() {
    BST tree;
    for (int value : {8, 3, 10, 1, 6, 9, 14}) tree.insert(value);
    cout << "Found 6 in " << tree.search(6) << " comparisons\n";
}

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) {
            val = x;
        }
    }
    static class BST {
        TreeNode root;
        public void insert(int val) {
            if(root == null) {
                root = new TreeNode(val);
                return;
            }
            TreeNode node = root;
            while (true) {
                if (val < node.val) {
                    if(node.left == null) {
                        node.left = new TreeNode(val);
                        return;
                    }
                    node = node.left;
                } else {
                    if(node.right == null) {
                        node.right = new TreeNode(val);
                        return;
                    }
                    node = node.right;
                }
            }
        }
        public int search(int val) {
            TreeNode node = root;
            int steps = 0;
            while (node != null) {
                steps++;
                if (val == node.val) return steps;
                node = val < node.val ? node.left : node.right;
            }
            return -1;
        }
    }
    public static void main(String[] args) {
        BST tree = new BST();
        for (int value : new int[]{8, 3, 10, 1, 6, 9, 14}) tree.insert(value);
        System.out.println("Found 6 in " + tree.search(6) + " comparisons");
    }
}

Watch it run

Step through it

Running on tree = [8, 3, 10, 1, 6, 9, 14], find 6

Output

Read all 12 Steps

Empty An empty BST. The first value inserted becomes the root.
Insert 8 8 becomes the root — every later value is placed relative to it.
Insert 3 3 < 8, so go left. The left slot is empty, so 3 lands there.
Insert 10 10 > 8, so go right. 10 becomes the right child.
Insert 1 1 < 8 go left to 3; 1 < 3 go left again. Empty, so 1 lands there.
Insert 6 6 < 8 go left; 6 > 3 go right. 6 becomes 3's right child.
Insert 9 9 > 8 go right; 9 < 10 go left. 9 lands as 10's left child.
Insert 14 14 > 8 then 14 > 10. 14 becomes 10's right child, completing the tree.
Search 6 Now search for 6. Every comparison discards one whole subtree.
6 < 8 Go left. The entire right subtree — 10, 9, 14 — is eliminated in one step.
6 > 3 Go right. Node 1 is eliminated too.
Found 6 matches. Three comparisons located it among seven nodes — that is the log N shape.

In-Order Traversal, and the Imbalance Problem

Traversing left subtree, then node, then right subtree — in-order — visits the keys in ascending sorted order. This falls directly out of the invariant: everything left of a node is smaller and everything right is larger, so visiting in that sequence is sorted by construction.

It gives several things for free. Sorted output in O(n) without a sort. A clean BST validation: run an in-order traversal and confirm each key exceeds the previous, which is a simpler alternative to the bounds method. And the kth smallest element by counting nodes as they are visited, or in O(h) if each node stores its subtree size.

Now the weakness that motivates everything built on top of BSTs. The structure has no mechanism to control its own shape — insertion attaches leaves wherever the search lands, and the resulting height depends entirely on the order keys arrive in.

Random insertion order gives an expected height of about 1.39 log₂ n, which is fine. But inserting already-sorted data produces a tree where every node has only a right child: a linked list with tree vocabulary, height n − 1, and every operation degraded to O(n).

This is not an obscure worst case. Sorted or nearly-sorted input is extremely common — timestamps, auto-increment identifiers, alphabetised names — and the failure is silent, since the code remains correct and small shuffled tests pass.

The fix is a self-balancing BST that restructures after modifications using rotations — local rearrangements that change the shape while preserving the ordering. AVL trees keep subtree heights within one of each other, staying shorter and favouring lookup-heavy workloads. Red-black trees enforce a looser colour invariant bounding the height at 2·log₂(n+1), rebalancing less often and favouring modification-heavy ones — which is why std::map, TreeMap and most library ordered containers use them.

The reason to accept O(log n) here rather than a hash table's O(1) is what the ordering provides: range queries, sorted iteration, and floor and ceiling lookups, none of which a hash table can answer at any price.

In-order traversal emits keys in sorted order, in O(n)
Validate by checking each in-order key exceeds the previous
Sorted input builds a degenerate tree — every operation becomes O(n)
AVL and red-black trees rotate to keep the height logarithmic