Binary search trees

A service keeps configuration revisions keyed by their activation times. To explain a request made at time 7, the debugger needs the latest revision active no later than 7, not merely an exact timestamp match.

A hash set handles membership, but this is an ordered-neighbor query. A binary search tree can discard an entire subtree on each comparison while keeping the best earlier key seen so far.

Finding the configuration active at a time

A BST maintains every left key smaller and every right key larger. Floor search retains the latest key not exceeding the query: a too-large node rules out its right subtree; an eligible node permits a larger answer only in its right subtree. Search and updates take O(h), with h potentially n in an unbalanced tree.

Keeping the closest earlier key

In a tree containing 8, 3, 12, 6, a floor query for 7 rejects 8 and moves left. At 3, save a legal candidate and look right for a closer one. At 6, improve the candidate again. An empty next link ends the search with 6; if no visited key was legal, the result is absent rather than an invented zero.

using Result=std::variant<bool,Int,std::monostate>;
Result changed=true;
Result floor=Int{3}; // preserve the distinction between bool and integer

Insertion order can turn the tree into a chain

Deletion with two children can replace a key with its inorder successor, then remove that successor in the right subtree. Owning unique_ptr links make subtree replacement explicit and avoid leaks. Duplicate add is a no-op, and removing a missing key is false. An unsorted unique list is a useful prototype because its behavior can be compared independently. The final exercise asks for an actual BST, rather than delegating to std::set; tests verify results but a complexity claim still requires reviewing structure.

Search, insertion, and deletion take O(h) for tree height h; storing the nodes takes O(n). Without balancing, sorted arrivals can produce h=n. A hash set is useful for equality lookup, and a sorted array for mostly static ordered queries, but neither has the same update tradeoffs.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

For revisions arriving in timestamp order, inspect the resulting tree height rather than assume the lookup stayed logarithmic.