Binary trees and binary search trees

A binary tree is a linked structure where each node has up to two children. A binary search tree adds one rule — the invariant — that makes searching fast. This lesson is about stating that invariant precisely, keeping it through insert and erase, walking trees in every order, and the trap every tree implementation falls into first: recursion as deep as the tree.

1. Vocabulary

Tree vocabulary

Root 8 (depth 0); leaves 1, 6, 14; height 3 (nodes on the longest root-to-leaf path). ∅ marks an empty child: order matters — 14 is 10's right child.

Height here counts nodes on the longest root-to-leaf path: 0 for an empty tree, 1 for a single node. (Some books count edges; be explicit.)
A tree of n nodes has height between ⌈log₂(n+1)⌉ (perfectly balanced) and n (a chain).

2. Traversals

Four classic orders, each with a use:

Order	Visit	Typical use
pre-order	node, left, right	copy / serialise a tree
in-order	left, node, right	sorted order of a BST
post-order	left, right, node	free / evaluate children first
level-order	depth 0, then 1, …	shortest paths, printing by level

The recursive versions are three lines each:

C++

#include <memory>
#include <print>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
};

std::unique_ptr<Node> leaf(int k) { return std::make_unique<Node>(k); }

void preorder(const Node* n) {
    if (!n) return;
    std::print("{} ", n->key);
    preorder(n->left.get());
    preorder(n->right.get());
}

void inorder(const Node* n) {
    if (!n) return;
    inorder(n->left.get());
    std::print("{} ", n->key);
    inorder(n->right.get());
}

int main() {
    auto root = leaf(8);
    root->left = leaf(3);
    root->left->left = leaf(1);
    root->left->right = leaf(6);
    root->right = leaf(10);
    preorder(root.get());
    std::println();
    inorder(root.get());   // sorted: this is a BST
    std::println();
}

Recursion uses one stack frame per level. For a balanced tree that's ~20 frames for a million nodes — fine. For a chain it's a million frames — a crash (§6). The iterative versions replace the call stack with an explicit one:

C++

#include <memory>
#include <print>
#include <queue>
#include <vector>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
};

// In-order without recursion: go left as far as possible, pushing the path;
// pop a node, visit it, then do the same for its right subtree.
void inorder(const Node* n) {
    std::vector<const Node*> stack;
    while (n || !stack.empty()) {
        while (n) {
            stack.push_back(n);
            n = n->left.get();
        }
        n = stack.back();
        stack.pop_back();
        std::print("{} ", n->key);
        n = n->right.get();
    }
    std::println();
}

// Level order: a queue instead of a stack.
void levels(const Node* root) {
    std::queue<const Node*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        const Node* n = q.front();
        q.pop();
        std::print("{} ", n->key);
        if (n->left) q.push(n->left.get());
        if (n->right) q.push(n->right.get());
    }
    std::println();
}

int main() {
    auto root = std::make_unique<Node>(8);
    root->left = std::make_unique<Node>(3);
    root->right = std::make_unique<Node>(10);
    root->left->right = std::make_unique<Node>(6);
    inorder(root.get());   // 3 6 8 10
    levels(root.get());    // 8 3 10 6
}

3. The BST invariant — precisely

For every node: all keys in its left subtree are smaller than its key, and all keys in its right subtree are larger.

It's about whole subtrees, not just children. This tree satisfies every parent–child comparison and is not a BST:

Every parent–child pair is fine, and it's still not a BST

parent–child checks pass

bounds passed down: (lo, hi)

Inherited bounds catch it: the left subtree of 5 allows only keys in (−∞, 5), and 3's right subtree narrows that to (3, 5). 6 is outside.

The robust check passes an allowed range down the tree. Every node narrows it for its children:

C++

#include <memory>
#include <optional>
#include <print>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
};

// Every key in this subtree must lie strictly inside (lo, hi).
bool valid(const Node* n, std::optional<int> lo, std::optional<int> hi) {
    if (!n) return true;
    if ((lo && n->key <= *lo) || (hi && n->key >= *hi)) return false;
    return valid(n->left.get(), lo, n->key) && valid(n->right.get(), n->key, hi);
}

int main() {
    auto root = std::make_unique<Node>(5);
    root->left = std::make_unique<Node>(3);
    root->left->right = std::make_unique<Node>(6);
    std::println("valid: {}", valid(root.get(), std::nullopt, std::nullopt));  // false
}

(Recursive for clarity; the build task asks for an iterative version — a stack of (node, lo, hi) frames does the same job.) Strict < means no duplicates: this tree is a set. Multisets put equal keys consistently on one side.

4. Search and insert

Both are one loop: compare, go left or right, stop at the key or at a null child. The neat trick for insert is to walk with a pointer to the owning slot — the unique_ptr you'll fill — so the empty tree isn't a special case:

insert(7): walk the owning slot down to a null child

start / 4

Compare and go left or right until the slot is empty, then fill it. The walk is O(height).

C++

#include <memory>
#include <print>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
};

bool insert(std::unique_ptr<Node>& root, int key) {
    std::unique_ptr<Node>* slot = &root;
    while (*slot) {
        Node* n = slot->get();
        if (key < n->key)      slot = &n->left;
        else if (n->key < key) slot = &n->right;
        else                   return false;   // already present
    }
    *slot = std::make_unique<Node>(key);
    return true;
}

int main() {
    std::unique_ptr<Node> root;
    for (int k : {8, 3, 10, 1, 6, 3}) std::print("{} ", insert(root, k));
    std::println();
}

Search costs O(height). Insert keys in random order and the expected height is about 2.99·log₂ n; insert them sorted and every key goes right: the tree is a linked list and every operation is O(n).

Same keys, different insertion orders

insert 3, 1, 4, 2, 5

insert 1, 2, 3, 4, 5 (sorted)

Random order gives height about 2.99·log₂ n on average. Sorted order sends every key right: a linked list with extra pointers, O(n) per operation — and n levels of recursion.

5. Erase: three cases

Leaf — remove it.
One child — the child takes the node's place.
Two children — find the successor (the leftmost node of the right subtree, i.e. the next key in order). Copy its key into the node, then remove the successor — which has no left child, so it's case 1 or 2.

erase(3): two children, so the successor's key moves up

before

after

The successor is the leftmost node of 3's right subtree: 4. Copy 4 into the node, then remove 4's old node — it has no left child, so that's case 1 or 2.

With parent pointers there's a fourth thing to keep right: when a child moves up, its parent must point at its new parent. Forget it and the next in-order walk climbs into a node that no longer exists.

Worked example: erase with `unique_ptr` and parent pointers

C++

bool erase(const K& key) {
    Node* n = find(key);
    if (!n) return false;
    if (n->left && n->right) {                 // case 3 → reduce to 1/2
        Node* s = leftmost(n->right.get());
        n->key = std::move(s->key);
        n = s;
    }
    std::unique_ptr<Node> child = std::move(n->left ? n->left : n->right);
    if (child) child->parent = n->parent;      // child moves up
    owner(n) = std::move(child);               // owner: parent's left/right or root; destroys n
    --size_;
    return true;
}

owner(n) returns the unique_ptr that holds n. Assigning the child into it both re-links the tree and destroys n — so nothing may touch n afterwards.

Faded example: lower_bound on a BST

lower_bound(key) is the smallest key >= key. Fill in the two branches:

C++

const Node* lower_bound(const Node* n, const K& key) {
    const Node* best = nullptr;
    while (n) {
        if (n->key < key) { /* ??? */ }
        else              { /* ??? */ }
    }
    return best;
}

Answer

If n->key < key, everything in n's left subtree is too small as well: go right (n = n->right.get()). Otherwise n is a candidate — record best = n — and a smaller candidate can only be on the left: n = n->left.get().

6. Recursion depth: the degenerate-tree trap

unique_ptr ownership makes destruction automatic — and recursive: destroying the root destroys its children, which destroy theirs. For a chain of n nodes that's n nested destructor calls. Thread stacks are typically 8 MiB (secondary threads often much less), and with sanitizers each frame is larger: a few thousand levels can be enough to overflow.

The fix is to tear down with an explicit stack, moving children out before each node dies:

C++

#include <memory>
#include <print>
#include <vector>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
};

void destroy(std::unique_ptr<Node> root) {
    std::vector<std::unique_ptr<Node>> stack;
    if (root) stack.push_back(std::move(root));
    while (!stack.empty()) {
        std::unique_ptr<Node> n = std::move(stack.back());
        stack.pop_back();
        if (n->left) stack.push_back(std::move(n->left));
        if (n->right) stack.push_back(std::move(n->right));
        // n dies here with no children: no recursion
    }
}

int main() {
    std::unique_ptr<Node> root = std::make_unique<Node>(0);
    Node* tail = root.get();
    for (int i = 1; i < 200'000; ++i) {          // a 200,000-deep chain
        tail->right = std::make_unique<Node>(i);
        tail = tail->right.get();
    }
    destroy(std::move(root));
    std::println("destroyed without recursion");
}

The same goes for anything you'd write recursively — height, validation, traversal, copying: fine on balanced trees, a crash on degenerate ones. Real balanced trees (Level 6) bound the height at O(log n) and make recursion safe again.

7. An in-order iterator

With parent pointers, ++ needs no stack:

If the node has a right subtree, the successor is that subtree's leftmost node.
Otherwise, climb until you come up from a left child; that parent is next. If you run out of parents, you were at the largest key: you're at end().

C++

iterator& operator++() {
    if (node_->right) {
        node_ = leftmost(node_->right.get());
    } else {
        const Node* child = node_;
        node_ = node_->parent;
        while (node_ && child == node_->right.get()) {
            child = node_;
            node_ = node_->parent;
        }
    }
    return *this;
}

++ from 6: no right subtree, so climb

start / 3

Climb while you come up from a right child; the first parent you reach from a left child is next. Over a whole traversal every edge is walked down once and up once.

Over a full traversal every edge is walked down once and up once, so iterating n keys is O(n): amortised O(1) per ++, even though one step can climb far.

8. `std::set` and `std::map`

The standard ordered containers are balanced BSTs (red-black trees in libstdc++, libc++ and MSVC): O(log n) guaranteed, in-order iteration, parent pointers inside. You get the BST vocabulary for free:

C++

#include <print>
#include <set>

int main() {
    std::set<int> s{40, 10, 30, 20};
    std::println("first >= 25: {}", *s.lower_bound(25));
    std::println("first >  30: {}", *s.upper_bound(30));
    auto [it, inserted] = s.insert(30);
    std::println("insert 30 again: {}", inserted);
    for (int k : s) std::print("{} ", k);   // sorted
    std::println();
}

Use them in real code. Write your own when you need something they don't give you — order statistics, augmented data per node, intrusive nodes — which is what the coming levels build on.

Summary

Traversals: pre (copy), in (sorted), post (free), level (by depth).
The BST invariant constrains whole subtrees; validate with inherited (low, high) bounds, not parent–child comparisons.
Insert by walking a pointer to the owning unique_ptr slot.
Erase: leaf, one child, two children → swap in the successor's key and remove it. Keep parent pointers right.
Height is O(log n) for random inserts and O(n) for sorted ones — so nothing may recurse per level, including the destructor.

Color theme

Binary trees and binary search trees

1. Vocabulary

2. Traversals

3. The BST invariant — precisely

4. Search and insert

5. Erase: three cases

Worked example: erase with `unique_ptr` and parent pointers

Faded example: lower_bound on a BST

6. Recursion depth: the degenerate-tree trap

7. An in-order iterator

8. `std::set` and `std::map`

Summary

Watch & read

1. Vocabulary

2. Traversals

3. The BST invariant — precisely

4. Search and insert

5. Erase: three cases

Worked example: erase with unique_ptr and parent pointers

Faded example: lower_bound on a BST

6. Recursion depth: the degenerate-tree trap

7. An in-order iterator

8. std::set and std::map

Summary

Worked example: erase with `unique_ptr` and parent pointers

8. `std::set` and `std::map`