EECS 280, Programming and Introductory Data Structures
Binary Search Tree and Map
A templated binary search tree with a custom comparator and in-order iterator, wrapped into an associative Map<Key, Value> container.
What I built
- Implemented BinarySearchTree<T, Compare> with recursive static helpers for size, height, deep copy, destroy, find, insert, min/max element, min-greater-than, sorting-invariant check, and in-order and pre-order traversal.
- Wrote an in-order Iterator that steps to the leftmost node of the right subtree or falls back to a min-greater-than search from the root.
- Built Map<Key, Value> on the BST using a pair comparator that orders by key only, with find, insert returning (iterator, bool), and operator[] that inserts a default value on a miss.
- Wrote 27 BST unit tests compiled with AddressSanitizer and UBSan.