09. Binary Search Trees

Trees, subtrees and the search rule#

A tree is a connected structure of nodes with no cycles. Once a root is chosen, each other node has exactly one parent; following links away from the root leads to its children. A leaf has no children; an internal node has at least one. A binary tree has at most two children per node, with distinct left and right positions.

The subtree rooted at a node consists of that node and all its descendants. This gives trees their natural recursion: a tree is either empty, or a root with a left tree and a right tree. A null child is an empty subtree, not an extra stored node.

For the strict, duplicate-free BST used here, every value in a node's left subtree is smaller than its value, and every value in its right subtree is larger. Both subtrees obey the same rule. The condition applies to all descendants, not just the immediate children.

For example, root 10 with left child 5 and 5's right child 12 is invalid: 12 is greater than its immediate parent but lies in 10's left subtree. Search for 12 would go right at 10 and miss it.

The lecture picture connects the conceptual tree with memory. Each stored node holds one integer and two child pointers. Crossed boxes at leaves represent null pointers.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
typedef struct node Node;
struct node { int item; Node *left, *right; };
Node *newNode(int v) {
    Node *p = malloc(sizeof *p);
    if (p == NULL) abort();
    *p = (Node){.item = v, .left = NULL, .right = NULL};
    return p;
}

The slides also show a recursion-call tree and a Morse-code decoding tree. Both are trees because they branch hierarchically, but neither is automatically a binary search tree: only a BST adds the numeric/order comparison invariant. A binary tree can have left and right children without being searchable by comparing the target with its root.

A root pointer is enough to reach the entire structure. Nodes need not occupy neighbouring addresses. A pointer assignment changes a connection; it does not copy every node below it.

Height controls path length#

The depth of a node is its number of edges from the root. The height of a nonempty tree is its maximum root-to-leaf edge distance. A leaf therefore has height 0. Define empty-tree height as $-1$ so the recurrence works uniformly:

$$h(t)=1+\max(h(t_L),h(t_R)),\qquad h(\varnothing)=-1.$$

The highlighted lecture path has three edges, so height is 3 even though it contains four nodes.

For $n\geq1$ nodes, maximum height is $n-1$: every node can have only one child, forming a chain. A height-$h$ binary tree holds at most $1+2+\cdots+2^h=2^{h+1}-1$ nodes. Therefore minimum possible height is $\lceil\log_2(n+1)\rceil-1=\lfloor\log_2 n\rfloor$. These exact integer bounds explain the logarithmic best shape and linear worst shape.

The slides call a tree of minimum possible height balanced, a maximum-height chain degenerate, and an intermediate shape unbalanced. These labels describe the present shape; they are not a promise that future plain BST updates preserve a minimum height. The stricter recursive size- and height-balance tests come in 10. Balancing Binary Search Trees.

Practice. Does a tree of height 3 necessarily have 15 nodes? Can it have 3 nodes?

Insertion and search follow one branch#

Build a tree by insertion#

To insert $v$, compare it with the current root. Smaller means insert into the left subtree; larger means the right. Reaching null creates a node at that position. Equal means return unchanged, giving set-like duplicate handling.

Node *bstInsert(Node *t, int v) {
    if (t == NULL) return newNode(v);
    if (v < t->item) t->left = bstInsert(t->left, v);
    else if (v > t->item) t->right = bstInsert(t->right, v);
    return t;
}

The function returns the root of the updated subtree. The assignment t->left = ... matters because inserting into a previously null child creates a different root pointer for that child. The client similarly writes root = bstInsert(root, v), especially when the entire tree starts empty.

Insert 4,2,6,5,1,7,3. Four becomes the root. Two is smaller, so becomes its left child; 6 becomes its right child. Five takes right at 4 then left at 6. The remaining insertions fill the positions shown below. No array suffix moves.

Watch for the empty child where a value is attached. The built-in also ignores duplicates, matching the implementation above. Repeating 6 leaves seven nodes, rather than adding an eighth occurrence.

The correctness argument follows the recursive structure. At a null subtree a single leaf is a valid BST. If $v$ is smaller than the root, only the left subtree needs changing, and inserting there retains the ancestor's upper bound; the corresponding statement holds on the right. Existing connections outside the chosen branch remain unchanged. Each recursive call moves one level down, so a finite tree eventually reaches null or equality.

Practice. In that final tree, where does 0 go? Why would setting t->left to a new node immediately at root 4 lose information?

Insertion order changes the shape#

Insert 5,6,2,3,4,7,1. The values are still 1 through 7, but 3 becomes the right child of 2 and 4 the right child of 3. Height is now 3 rather than 2.

Insert the same values in ascending order and every next value goes right, giving height 6:

The BST invariant guarantees correct search directions; it does not guarantee that each direction discards half of the nodes. Building an ascending $n$-node tree costs $0+1+\cdots+(n-1)=\Theta(n^2)$ comparisons up to constant terms. This is construction cost, distinct from one later search.

Search and an absent target#

bool bstSearch(const Node *t, int v) {
    while (t != NULL) {
        if (v == t->item) return true;
        t = v < t->item ? t->left : t->right;
    }
    return false;
}

The loop invariant is: if the target occurs in the original tree and has not already been found, it occurs in the current candidate subtree. If $v$ is smaller than the root, the root and entire right subtree cannot match. Moving left therefore retains every possible answer. Null means no candidate remains.

For the irregular lecture tree above, search for 4 compares 5,2,3,4: left, right, right, found. Search for 9 compares 5,6,7 then reaches null to the right of 7. The unsuccessful search does not need to visit 2,1,3 or 4.

With height $h$, a path contains at most $h+1$ stored nodes, so search and insertion have worst-case $O(h+1)$ time. This avoids treating the height-zero case as zero work. A chain gives $O(n)$; a logarithmic-height tree gives $O(\log(n+1))$. Best-case successful search finds the root in $O(1)$.

An average $O(\log n)$ claim for an ordinary BST needs an input assumption, typically uniformly random insertion order of distinct keys. It is not an unconditional guarantee. The iterative search uses $O(1)$ auxiliary space. Recursive search/insertion uses $O(h+1)$ call-stack space including the final null call; the nodes themselves use $\Theta(n)$ storage.

Practice. Does a search take logarithmic time merely because it makes two-way comparisons?

Join and deletion#

Join two already ordered trees#

bstJoin(a,b) combines two disjoint trees under the precondition that every value in a is smaller than every value in b. It is not a general union operation. An empty input simply returns the other input.

For nonempty inputs, find the minimum node in b, which is its leftmost node. Detach it from its old position, replacing it with its right subtree if present. Make that minimum the new root, with a on the left and the remainder of b on the right.

Node *bstJoin(Node *a, Node *b) {
    if (a == NULL) return b;
    if (b == NULL) return a;
    if (b->left == NULL) { b->left = a; return b; }
    Node *parent = b, *min = b->left;
    while (min->left != NULL) {
        parent = min;
        min = min->left;
    }
    parent->left = min->right;
    min->left = a;
    min->right = b;
    return min;
}

Why retain min->right? A minimum has no left child, but may have larger descendants on its right. They remain smaller than its old parent and can replace it there. Overwriting the old parent's link with null would lose them. If b itself is minimum, handle that separately; setting min->right=b when they are the same node would make a cycle.

For the lecture's join trace, let a have root 10 and children 5,14; let b have root 30, left child 24 (whose right child is 29 with left child 26), and right child 32. Every a key is below every b key. The minimum in b is 24. Its right subtree 29 replaces it as 30's left child, carrying 26 along. Promote 24, attach a as its left subtree and the modified b as its right. Inorder before and after is 5,10,14,24,26,29,30,32. In particular, replacing 24 by null in its former location would discard 29 and 26.

No nodes are allocated or freed by join. The two input root handles are consumed as separate trees: afterward they point into one shared result and must not be independently freed. Following the left spine of b costs $O(h_b+1)$ time and $O(1)$ auxiliary space.

Practice. Can you join a tree containing 2,8 with a tree containing 5,10 using this method?

Delete by replacing a subtree root#

Search for the requested value as usual. Once found, there are three structural cases: a leaf becomes null; a node with one child is replaced by that child; a node with two children is replaced by joining its left and right trees. These children satisfy join's ordering precondition because the original tree was a BST.

Node *bstDelete(Node *t, int v) {
    if (t == NULL) return NULL;
    if (v < t->item) t->left = bstDelete(t->left, v);
    else if (v > t->item) t->right = bstDelete(t->right, v);
    else {
        Node *replacement = bstJoin(t->left, t->right);
        free(t);
        return replacement;
    }
    return t;
}

The empty-input return also handles an absent key without altering membership. Always retain the returned root: root = bstDelete(root, v). Free exactly the removed node; its retained children belong to the replacement tree.

The lecture builds deletion from small cases before the successor case. If the entire tree is a leaf 5, deleting 5 returns NULL. If root 5 has only right child 6, whose right child is 7, deleting 5 returns subtree root 6 and retains 7. If root 5 has left child 4 and right child 6 (with right child 7), deleting 5 can promote successor 6; its left is 4 and right is 7. In all three cases the caller replaces its old pointer with the returned root. The two-child example is not a special instruction to copy 6 without removing its original node.

The inorder successor is the next larger value in sorted order. For a node with a right subtree, it is the minimum of that subtree. Similarly, the inorder predecessor is the maximum of its left subtree. A general successor for a node with no right subtree may instead be an ancestor; the deletion case here only needs the right-subtree form.

In the lecture example, deleting 12 below root 23 uses successor 13. The old 13 has right child 14, so 14 replaces it as 15's left child. The replacement root 13 takes the old left subtree rooted at 5 and the right subtree rooted at 15:

A second valid implementation copies the successor's value into the found node and recursively deletes the successor from the right subtree. This removes a different allocated node but produces the same abstract set. It must not leave two copies of the successor. 11. AVL Trees uses this version so every affected recursive ancestor is rebalanced.

Search to the deletion point plus the successor path stays within $O(h+1)$ time. Recursive deletion takes $O(h+1)$ call-stack space; join itself above is iterative. Neither variant guarantees the resulting tree remains balanced.

Practice. Why not replace a two-child node by any value in its right subtree?

Traversal visits the entire tree#

A traversal systematically visits every node. Its order is chosen by where the root visit sits relative to the left and right recursive calls:

For the lecture tree with root 23, left subtree 13 (left 5, right 15 with left 14), and right subtree 43 (right 67), inorder produces the ascending sequence pictured below.

The other orders are preorder 23,13,5,15,14,43,67, postorder 5,14,15,13,67,43,23, and level order 23,13,43,5,15,67,14. Trace the subtrees as complete units rather than sorting the values mentally.

void bstPreorder(const Node *t, void (*visit)(int)) {
    if (t == NULL) return;
    visit(t->item);
    bstPreorder(t->left, visit);
    bstPreorder(t->right, visit);
}
void bstPostorder(const Node *t, void (*visit)(int)) {
    if (t == NULL) return;
    bstPostorder(t->left, visit);
    bstPostorder(t->right, visit);
    visit(t->item);
}
void bstInorder(const Node *t, void (*visit)(int)) {
    if (t == NULL) return;
    bstInorder(t->left, visit);
    visit(t->item);
    bstInorder(t->right, visit);
}
void bstFree(Node *t) {
    if (t == NULL) return;
    bstFree(t->left);
    bstFree(t->right);
    free(t);
}
size_t bstSize(const Node *t) {
    return t == NULL ? 0 : 1 + bstSize(t->left) + bstSize(t->right);
}
int bstHeight(const Node *t) {
    if (t == NULL) return -1;
    int l = bstHeight(t->left), r = bstHeight(t->right);
    return 1 + (l > r ? l : r);
}

The callback visit tells inorder what to do with a value; it need not print. Inorder is sorted because every left value precedes and is smaller than the root, and every right value follows and is larger. Induction applies the same reasoning within each subtree.

For level order, enqueue the nonnull root. While the queue is nonempty, dequeue one node, visit it, then enqueue its nonnull left and right children. FIFO ensures all previously discovered nodes at a shallower depth are processed first. The queue must hold node pointers in this use, so adapt the integer queue's item type accordingly.

All four traversals visit $n$ nodes exactly once, so take $\Theta(n)$ time for a constant-time visit, regardless of height. Recursive depth-first traversals, size and height use $O(h+1)$ stack space. Level order needs $O(w)$ queue space, where $w$ is maximum level width; worst case $O(n)$. A balanced tree has shallow recursion but may have a wide queue. Printing $n$ items also inherently requires linear output work.

Preorder alone does not uniquely encode an arbitrary binary tree unless null positions or other structural information are retained. The distinct-key BST ordering rule is what lets preorder act as a reconstruction insertion order here.

Practice. Give the four traversal orders for the perfect seven-node tree rooted at 4 from the insertion example.

Prune outside an inclusive range#

The lecture's pruning exercise removes every value outside $[lo,hi]$, assuming $lo\leq hi$. If the root is below lo, its entire left subtree is also below lo, so free it and the root, then continue in the right subtree. The symmetric case applies above hi. An in-range root retains both recursively pruned children.

Node *bstPrune(Node *t, int lo, int hi) {
    if (t == NULL) return NULL;
    if (t->item < lo) {
        Node *keep = t->right;
        bstFree(t->left);
        free(t);
        return bstPrune(keep, lo, hi);
    }
    if (t->item > hi) {
        Node *keep = t->left;
        bstFree(t->right);
        free(t);
        return bstPrune(keep, lo, hi);
    }
    t->left = bstPrune(t->left, lo, hi);
    t->right = bstPrune(t->right, lo, hi);
    return t;
}

This frees removed nodes as well as detaching them. Every original node is processed or freed at most once, so worst-case time is $O(n)$, including disposal, with $O(h+1)$ recursive space. It would be misleading to call deleting a large discarded subtree constant time merely because detaching its root pointer is constant work.

Practice. Prune the seven-node tree to $[3,6]$. Which values remain and what is the root?

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. Insert 8,4,12,2,6,10,14 into an empty BST. Give the inorder and preorder traversals.

Question 2. Delete root 8 from that BST using its inorder successor. Which key replaces it, and what link must be removed afterward?

Question 3. Two BSTs contain keys strictly below and strictly above 20 respectively. Under what condition can a join(left,right) routine safely combine them?