Binary search tree

A binary search tree (BST) is a Binary tree with an ordering invariant: for every node $X$,

• all values in $X$‘s left subtree are less than $X$.
• all values in $X$‘s right subtree are greater than $X$.

This invariant makes searching, insertion, and deletion all $O(h)$ where $h$ is the tree’s height. For a balanced tree, $h=O(\log n)$ — dramatically faster than scanning a list. For a degenerate (chain-like) tree, $h=O(n)$ — no faster than a linked list. Hence the importance of self-balancing variants like AVL trees and red-black trees.

Searching a BST

To search for value $V$:

1. Start at the root.
2. If $V$ equals the current node, return found.
3. If $V$ is less, descend to the left subtree.
4. If $V$ is greater, descend to the right subtree.
5. If you hit NULL, $V$ isn’t in the tree.

In the example, searching for “Gary”: start at “Larry” (Gary < Larry, go left), then “Fran” (Gary > Fran, go right), then “Gary” — found.

Iterative version:

int search(node *root, int V) {
    node *ptr = root;
    while (ptr != NULL) {
        if      (V == ptr->data) return 1;
        else if (V <  ptr->data) ptr = ptr->left;
        else                     ptr = ptr->right;
    }
    return 0;
}

Recursive version:

int search(node *ptr, int V) {
    if (ptr == NULL) return 0;
    if (V == ptr->data) return 1;
    if (V <  ptr->data) return search(ptr->left,  V);
    else                return search(ptr->right, V);
}

The recursive version is more elegant; the iterative one is slightly faster (no function-call overhead).

Big O of BST search

At each step you eliminate roughly half the remaining tree. With $N$ nodes, after $k$ steps you’ve narrowed down to $N/2^k$. Set this to 1: $2^k=N$, so $k={\log }_{2}N$.

So search is $O({\log }_{2}n)$ when the tree is balanced. Caveat: if the BST is a chain (built by inserting already-sorted data), search degenerates to $O(n)$.

Inserting

To preserve the BST invariant, the new value goes wherever the search for it would have ended (at a NULL slot):

If tree is empty:
    Allocate a new node, set as root.
Otherwise, start at root. While not done:
    If V equals current node: done (already in tree).
    If V < current node:
        If left child exists, descend left.
        Else, allocate new node and set as left child.
    If V > current node:
        If right child exists, descend right.
        Else, allocate new node and set as right child.

Iterative:

void Insert(BinaryTreeNode **node, int V) {
    BinaryTreeNode *temp = newNode(V);
    if (*node == NULL) {
        *node = temp;
        return;
    }
    BinaryTreeNode *current = *node;
    while (current != NULL) {
        if (V > current->data) {
            if (current->right == NULL) { current->right = temp; return; }
            current = current->right;
        } else if (V < current->data) {
            if (current->left == NULL) { current->left = temp; return; }
            current = current->left;
        } else {
            return;   // value already present, do nothing
        }
    }
}

Insertion is $O({\log }_{2}n)$ for balanced trees, $O(n)$ for degenerate ones — same as search.

Deleting

Three cases based on the target node’s children.

Case 1: target is a leaf

Just unlink it from its parent (set parent’s pointer to NULL) and free the node. If the target is the root, set root to NULL.

Case 2: target has one child

Splice the child up to take the target’s place — point the parent at the target’s only child, then free the target. If the target is the root, the only child becomes the new root.

Case 3: target has two children

Trickiest case. Replace the target’s value with its in-order successor (smallest value in its right subtree) or in-order predecessor (largest in its left subtree). Then delete the successor/predecessor from its original position — by construction it has at most one child, falling into Case 1 or 2.

The in-order successor of a node with two children can’t have a left child (otherwise that left child would be smaller, hence the successor). Same logic for the predecessor and right child. So the recursive deletion is well-defined.

BinaryTreeNode *Delete(BinaryTreeNode *node, int data) {
    if (node == NULL) return NULL;
    
    if (data < node->data) {
        node->left = Delete(node->left, data);
    } else if (data > node->data) {
        node->right = Delete(node->right, data);
    } else {
        // found the node; handle three cases
        // ...
    }
    return node;
}

The recursive form rebuilds the tree by returning the (possibly modified) subtree from each call.

Finding min and max

The minimum value is the leftmost node — keep going left until there’s no left child:

BinaryTreeNode *FindMin(BinaryTreeNode *node) {
    if (node == NULL) return NULL;
    if (node->left != NULL) return FindMin(node->left);
    return node;
}

The maximum is the rightmost — keep going right.

When BSTs go wrong

The big problem with plain BSTs: insertion order matters. Inserting 1, 2, 3, 4, 5 in order gives a right-skewed chain (every insertion goes right of the current node). The tree degenerates to height $O(n)$, so operations become $O(n)$ instead of $O(\log n)$.

Two solutions:

1. Insert in randomized order — works on average but not guaranteed.
2. Self-balancing trees: AVL tree, Red-black tree. These maintain a balance invariant during inserts and deletes, guaranteeing $O(\log n)$ regardless of input order.

This is why “real” BSTs in production code are always one of the balanced variants.

For the in-order traversal that produces sorted output from a BST, see Binary tree traversal.