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 turn: write Bst::insert (returns false for duplicates) and Bst::contains, both iterative.

Previous: Binary trees and recursion Next: Traversals and validation