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

Maintain an ordered set through insertion, removal, membership, and floor queries. The Boolean/Long/null result union must distinguish a failed mutation from a missing floor value.

An unsorted unique-key list makes updates simple but ordered queries require a scan. A BST uses subtree ordering to discard impossible keys. Deleting a two-child node must reconnect its replacement without losing the remaining subtree.

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.

A BST retains ordered subtrees: every left key is smaller, every right key larger. Removing a node with two children needs a successor/predecessor transplant without losing a subtree. Floor keeps the best key <= query while descending. Prototype may scan a unique-key list; final must build a BST, with O(h) operations and O(n) nodes; an unbalanced tree has h=n.

A floor search can retain an existing candidate while choosing which ordered region still contains a better answer:

import java.util.*;

class Example {
    public static void main(String[] args) {
        long rootKey = 5, query = 7;
        Long candidate = null;
        if (rootKey <= query) candidate = rootKey;
        assert candidate == 5L;
        assert query > rootKey; // a better floor, if present, must be to the right
    }
}

This is one search decision, not the complete traversal. If the root exceeded the query, its entire right subtree would be impossible. A hand-built unbalanced BST has O(height) operations and can degenerate to a chain; sorted input exposes that limit.

Insertion order can turn the tree into a chain

Ordered-set operations support predecessor lookups, range boundaries, and indexes. Use a balanced library tree in ordinary application code when custom node manipulation is not the purpose of the exercise.

Start empty. Commands add/remove return Boolean indicating a change; contains returns Boolean; floor returns the largest stored Long <= key or null. Return one result per command. Duplicate adds and missing removals are false. Unknown operation raises IllegalArgumentException. List<Object> intentionally models the Boolean/Long/null tagged result union.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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