Step 2 of 6

Binary search trees

A binary search tree (BST) keeps everything in a node's left subtree smaller than the node, and everything in its right subtree larger. Search then walks one path from the root, discarding half of a balanced tree at each step: O(log n).

std::map and std::set are balanced BSTs (red-black trees), which rebalance themselves so the height stays O(log n) even for sorted input. A plain BST can degrade into a linked list.

Insertion walks down to the empty spot where the key belongs. With a std::unique_ptr<Node>& you can follow the path by reference and assign into the right slot:

std::unique_ptr<Node>* slot = &root_;
while (*slot) slot = key < (*slot)->key ? &(*slot)->left : &(*slot)->right;
*slot = std::make_unique<Node>(key);

Your turn: write Bst::insert (returns false for duplicates) and Bst::contains, both iterative.

Previous: Binary trees and recursion Next: Traversals and validation