Binary Trees

The Gap We Are Trying to Close

Looking back at what we have built: arrays give $O(1)$ random access but $O(n)$ insertion. Linked lists give $O(1)$ front insertion but $O(n)$ access. Hash tables give $O(1)$ expected find but $O(n)$ for any order operation. Sorted arrays give $O(\log n)$ find but $O(n)$ insertion.

The unmet goal for both the Sequence and Set interfaces is $O(\log n)$ for every operation. Binary trees are the data structure built for exactly this. The key insight: if we can keep the tree's height $h = O(\log n)$, and every operation costs $O(h)$, then every operation costs $O(\log n)$.

The Node — Four Pointers

class Binary_Node:
    def __init__(self, x):      # O(1)
        self.item   = x
        self.left   = None      # left child
        self.right  = None      # right child
        self.parent = None      # parent node

    # ── TRAVERSAL ─────────────────────────────────────────
    def subtree_iter(self):     # O(n) — in-order traversal
        """Yield all nodes in this subtree in traversal order."""
        if self.left:
            yield from self.left.subtree_iter()
        yield self
        if self.right:
            yield from self.right.subtree_iter()

    # ── NAVIGATION ────────────────────────────────────────
    def subtree_first(self):    # O(h) — walk left until leaf
        """Return the first node in this subtree's traversal order."""
        if self.left:
            return self.left.subtree_first()
        return self

    def subtree_last(self):     # O(h) — walk right until leaf
        if self.right:
            return self.right.subtree_last()
        return self

    def successor(self):        # O(h) — next in traversal order
        """Return the node immediately after self in traversal order."""
        if self.right:
            return self.right.subtree_first()    # case 1: has right child
        # case 2: walk up until we come from a left subtree
        node = self
        while node.parent and (node is node.parent.right):
            node = node.parent
        return node.parent                       # None if self is last

    def predecessor(self):      # O(h) — previous in traversal order
        if self.left:
            return self.left.subtree_last()
        node = self
        while node.parent and (node is node.parent.left):
            node = node.parent
        return node.parent

#include <functional>
using namespace std;

template<typename T>
struct Binary_Node {
    T item;
    Binary_Node* left   = nullptr;
    Binary_Node* right  = nullptr;
    Binary_Node* parent = nullptr;

    Binary_Node(T x) : item(x) {}

    // In-order traversal — O(n)
    void subtree_iter(function<void(Binary_Node*)> visit) {
        if (left)  left->subtree_iter(visit);
        visit(this);
        if (right) right->subtree_iter(visit);
    }

    // Walk left until leaf — O(h)
    Binary_Node* subtree_first() {
        return left ? left->subtree_first() : this;
    }
    Binary_Node* subtree_last() {
        return right ? right->subtree_last() : this;
    }

    // Next in traversal order — O(h)
    Binary_Node* successor() {
        if (right) return right->subtree_first();
        auto* node = this;
        while (node->parent && node == node->parent->right)
            node = node->parent;
        return node->parent;   // nullptr if this is last
    }
    Binary_Node* predecessor() {
        if (left) return left->subtree_last();
        auto* node = this;
        while (node->parent && node == node->parent->left)
            node = node->parent;
        return node->parent;
    }
};

Terminology — Depth, Height, and Why They Matter

Every operation we will define on binary trees runs in $O(h)$ time, where $h$ is the height. A tree with $n$ nodes can have height anywhere from $\lfloor \log_2 n \rfloor$ (perfectly balanced) to $n-1$ (a chain — effectively a linked list). The entire enterprise of Chapters 6 and 7 is ensuring $h = O(\log n)$.

Traversal Order — The Central Concept

Every binary tree has a natural traversal order defined recursively: every node in a node's left subtree comes before it, and every node in the right subtree comes after it. The subtree_iter function above implements this — it is precisely in-order traversal.

Right now, this order has no semantic meaning. We will assign two different meanings to it:

Sequence interpretation: traversal order = sequence order. The $i$-th node in traversal order is the $i$-th item in the sequence. This gives us $O(h)$ get_at(i) and insert_at(i, x).

Set interpretation: traversal order = sorted order by key. This is the Binary Search Tree (BST) property. It gives us $O(h)$ find(k), find_next(k), find_prev(k).

Both interpretations share the same underlying node structure. Only the semantic meaning changes.

Tree Navigation — Four Operations, All O(h)

Four navigation operations form the backbone of everything we build on top of binary trees. Each runs in $O(h)$ by walking up or down the tree:

subtree_first(X) — walk left until you hit a node with no left child. That is the first node in $X$'s subtree. To find the minimum key in a BST: call subtree_first(root).

subtree_last(X) — symmetric. Walk right to find the last node.

successor(X) — two cases. If $X$ has a right child, the successor is the first node in the right subtree. If not, walk up until you come from a left child — that ancestor is the successor.

predecessor(X) — symmetric to successor.

Dynamic Operations — Inserting and Deleting Nodes

The tree only changes by adding or removing leaves — never internal nodes directly. This keeps the logic manageable. All dynamic operations run in $O(h)$.

Insert node $Y$ after node $X$ in traversal order: If $X$ has no right child, attach $Y$ as the right child. Otherwise, $X$'s successor has no left child (by definition of successor) — attach $Y$ as its left child.

Delete node $X$: If $X$ is a leaf, detach from parent. If not, swap $X$'s item with its predecessor (or successor if no predecessor), then recursively delete the node now holding $X$'s original item — which is one step closer to being a leaf. This recursion terminates because we always move down.

    def subtree_insert_before(self, B):   # O(h) — insert B before self
        if self.left:
            # self has a left child → insert B as rightmost node
            # of the left subtree (which has no right child)
            node = self.left.subtree_last()
            node.right  = B
            B.parent    = node
        else:
            # self has no left child → B becomes left child
            self.left   = B
            B.parent    = self

    def subtree_insert_after(self, B):    # O(h) — insert B after self
        if self.right:
            node = self.right.subtree_first()
            node.left   = B
            B.parent    = node
        else:
            self.right  = B
            B.parent    = self

    def subtree_delete(self):             # O(h)
        """Remove self from tree. Returns the node physically deleted (a leaf)."""
        if self.left or self.right:       # not a leaf — swap down first
            # choose predecessor if left child exists, else successor
            B = self.predecessor() if self.left else self.successor()
            self.item, B.item = B.item, self.item  # swap items
            return B.subtree_delete()               # now recurse on B
        # self is a leaf — detach from parent
        if self.parent:
            if self.parent.left is self:
                self.parent.left  = None
            else:
                self.parent.right = None
        return self

    void insert_before(Binary_Node* B) {  // O(h)
        if (left) {
            auto* node = left->subtree_last();
            node->right = B;
            B->parent   = node;
        } else {
            left     = B;
            B->parent = this;
        }
    }

    void insert_after(Binary_Node* B) {   // O(h)
        if (right) {
            auto* node = right->subtree_first();
            node->left = B;
            B->parent  = node;
        } else {
            right    = B;
            B->parent = this;
        }
    }

    Binary_Node* subtree_delete() {       // O(h)
        if (left || right) {
            auto* B = left ? predecessor() : successor();
            swap(item, B->item);          // swap items, not pointers
            return B->subtree_delete();   // recurse — always moves down
        }
        // self is a leaf
        if (parent) {
            if (parent->left  == this) parent->left  = nullptr;
            else                       parent->right = nullptr;
        }
        return this;
    }

Application: Binary Search Tree (Set Interface)

Assign the Set semantic to traversal order: the traversal order is sorted by key. This is the BST property: for every node, every key in the left subtree is smaller, every key in the right subtree is larger.

Finding key $k$ in a BST is like binary search, but on the tree structure instead of an array. At each node: if $k$ is smaller, recurse left; if larger, recurse right; if equal, found. Cost: $O(h)$.

class BST_Node(Binary_Node):
    """A Binary_Node where traversal order = sorted order by key."""

    def subtree_find(self, k):          # O(h)
        """Find node with key k in this subtree. Returns None if absent."""
        if k < self.item.key:
            return self.left.subtree_find(k)  if self.left  else None
        elif k > self.item.key:
            return self.right.subtree_find(k) if self.right else None
        else:
            return self                        # found

    def subtree_find_next(self, k):     # O(h) — smallest key > k
        if self.item.key <= k:
            return self.right.subtree_find_next(k) if self.right else None
        # self.item.key > k: check if left subtree has something better
        B = self.left.subtree_find_next(k) if self.left else None
        return B if B else self

    def subtree_find_prev(self, k):     # O(h) — largest key < k
        if self.item.key >= k:
            return self.left.subtree_find_prev(k) if self.left else None
        B = self.right.subtree_find_prev(k) if self.right else None
        return B if B else self

    def subtree_insert(self, B):        # O(h) — insert BST_Node B
        """Insert B maintaining BST property."""
        if B.item.key < self.item.key:
            if self.left:  self.left.subtree_insert(B)
            else:          self.subtree_insert_before(B)
        elif B.item.key > self.item.key:
            if self.right: self.right.subtree_insert(B)
            else:          self.subtree_insert_after(B)
        else:
            self.item = B.item           # duplicate key: update in place

template<typename T, typename K>
struct BST_Node : Binary_Node<T> {
    using Base = Binary_Node<T>;
    BST_Node(T x) : Base(x) {}

    // Find node with key k — O(h)
    BST_Node* subtree_find(K k) {
        if (k < this->item.key)
            return this->left  ? static_cast<BST_Node*>(this->left)->subtree_find(k)  : nullptr;
        if (k > this->item.key)
            return this->right ? static_cast<BST_Node*>(this->right)->subtree_find(k) : nullptr;
        return this;
    }

    // Insert BST_Node B maintaining sorted order — O(h)
    void subtree_insert(BST_Node* B) {
        if (B->item.key < this->item.key) {
            if (this->left)  static_cast<BST_Node*>(this->left)->subtree_insert(B);
            else             this->insert_before(B);
        } else if (B->item.key > this->item.key) {
            if (this->right) static_cast<BST_Node*>(this->right)->subtree_insert(B);
            else             this->insert_after(B);
        } else {
            this->item = B->item;  // update duplicate
        }
    }
};

Application: Sequence Binary Tree (Augmentation)

For the Sequence interface, traversal order = sequence order. The key operation is get_at(i) — find the $i$-th node in traversal order. Naively, iterate through the tree: $O(n)$. Better: augment each node with the size of its subtree.

With subtree sizes, get_at(i) becomes $O(h)$: check the left subtree size $n_L$. If $i < n_L$, recurse left. If $i > n_L$, recurse right with $i' = i - n_L - 1$. If $i = n_L$, return this node.

Maintaining subtree sizes costs $O(h)$ per insert or delete — just update all ancestors on the path to the root. This is the general principle of augmentation: add a field to each node, maintain it during modifications, and exploit it to answer queries faster.

Why $O(h)$ Is Not Yet $O(\log n)$

Everything above runs in $O(h)$. But we have not guaranteed $h = O(\log n)$. A BST built by inserting already-sorted keys degenerates into a linked list: height $n-1$, all operations $O(n)$.

This is the fundamental problem that Chapter 7 solves. AVL trees maintain a balance invariant — the heights of any node's left and right subtrees differ by at most 1. This guarantees $h = O(\log n)$ always, even after arbitrary insertions and deletions.

The Performance Picture So Far

(e) expected · (h) height of tree, can be O(n) without balance guarantee