Binary Search Tree & Map
A recursive, templated binary search tree that also powers a map of unique keys and their values.
See how it worksOverview
This C++ project builds a binary search tree and an associative map from linked nodes. A comparator determines key order, and recursive helpers handle insertion, search, traversal, copying, and destruction.
The browser animation follows the same ordering and map semantics with illustrative integer keys. The tree retains its insertion shape and does not rebalance.
How it works
- Insert at a leaf. Compare a new key with the current node, follow the left or right subtree, and allocate a node at the first empty position.
- Find a key. Use the same comparisons to narrow the search to one branch at a time. A successful search returns an iterator; a missing key returns the end iterator.
- Iterate in order. Begin at the minimum key and advance to each successor. Iteration yields keys in comparator order.
- Build a map. Store key-value pairs in the tree and compare only their keys. Accessing a missing key with
operator[]creates an entry with a value-initialized value.
Ownership and abstraction
The tree recursively copies its nodes and releases them on destruction. The map reuses that tree and its iterator, keeping key ordering separate from the mapped values.