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 binary search tree maintains smaller keys in every left subtree and larger keys in every right subtree. Search discards one whole subtree at each comparison. This invariant supports exact membership and floor queries: the largest stored integer no greater than a query.

An unsorted unique-key array is a useful prototype. It makes membership and removal simple to inspect, but floor and membership scans can require O(n) work.

Keeping the closest earlier key

For floor, retain the latest eligible key. A node above the query rules out its right subtree. A node at or below the query is a candidate, and only its right subtree might improve it. Returning the last visited node without tracking eligibility can return a key larger than the query.

Deletion has three structural cases. A leaf disappears; a one-child node is replaced by its child; a two-child node can use its inorder successor and then remove that successor from the right subtree. Updating the root is as important as updating an interior parent link. Duplicate add does not create duplicate keys, and missing remove must return false.

JavaScript Set supplies exact membership but no ordered floor operation; its iteration order is insertion order. The final exercise asks for an actual BST rather than sorting the entire set after every command. Return true/false for change and membership results, Numbers for present floors, and null for absent floors; 0 and false are distinct results.

const keys = new Set([3, 1, 5]);
console.log(keys.add(3).size); // 3: adding a duplicate does not grow a set
console.log(keys.has(0), 0 === false); // false false
const node = {key: 3, left: null, right: null};
console.log(node.key); // 3: child placement must maintain the BST invariant

Insertion order can turn the tree into a chain

BST operations take O(h) for height h. An ordinary unbalanced tree can become a chain, so O(log n) is not guaranteed without balancing. Ordered indexes are useful for predecessor/successor queries and dynamic keys; a hash Set can be preferable when only exact membership matters. Tests check observable deletion/floor behavior; inspect the implementation to justify its structure and complexity.

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