Step 2 of 6

Binary search trees

A binary search tree (BST) adds one rule to a binary tree: everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. That rule makes searching fast: at each node, you know which side the key must be on, so you walk one path from the root and ignore the rest.

        8
       / \
      3   10
     / \    \
    1   6    14

To find 6: 6 < 8, go left; 6 > 3, go right; found. Three steps instead of checking all six nodes.

#include <iostream>
#include <memory>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
    explicit Node(int k) : key(k) {}
};

void insert(std::unique_ptr<Node>& root, int key) {
    std::unique_ptr<Node>* slot = &root;          // a pointer to "the link we might fill"
    while (*slot) {
        slot = key < (*slot)->key ? &(*slot)->left : &(*slot)->right;
    }
    *slot = std::make_unique<Node>(key);          // fill the empty link
}

int depth_of(const Node* n, int key) {
    int depth = 0;
    while (n) {
        if (key == n->key) return depth;
        n = key < n->key ? n->left.get() : n->right.get();
        depth++;
    }
    return -1;
}

int main() {
    std::unique_ptr<Node> root;
    for (int k : {8, 3, 10, 1, 6, 14}) insert(root, k);
    std::cout << depth_of(root.get(), 6) << " " << depth_of(root.get(), 14) << " " << depth_of(root.get(), 5) << "\n";
}

2 2 -1

How insertion works

A new key always goes into an empty spot at the bottom: walk down as if searching, and when you reach a null link, put the new node there. The trick is slot: a pointer to the unique_ptr link itself, not to a node. Following it down the tree, you end up pointing at exactly the link to fill, whether that's root or some node's left or right.

Balance

On a balanced tree, each step discards about half the nodes, so search and insert are O(log n). But insert the keys in sorted order (1, 2, 3, 4, ...) and every node goes to the right: the "tree" becomes a linked list, and operations become O(n). std::map and std::set are self-balancing BSTs (red-black trees in every major standard library) that rotate nodes to keep the height O(log n) no matter the insertion order.

Your task

insert is the loop above, plus a duplicate check (if the key equals the node's key, return false) and size_++ on success. contains walks down the same way with a plain const Node*.

Your task

Write Bst::insert (returns false for duplicates) and Bst::contains, both iterative.

Challenge 2

Add std::optional<int> floor(int x) const to the BST: the largest key that is <= x, or std::nullopt if every key is bigger. Walk down from the root without recursion: going right is safe when the key is small enough, and remember the best candidate so far.

Challenge 3

Add bool erase(int key) to the BST. Find the link (std::unique_ptr<Node>*) that owns the node. With at most one child, replace the node with that child. With two children, copy the smallest key of the right subtree into the node, then remove that smallest node (it has no left child).

Previous: Binary trees and recursion Next: Traversals and validation