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

Each BST node divides keys into strictly smaller and strictly larger subtrees. Searching follows only one branch. Floor search remembers the best <= candidate when moving right. Removal must handle zero, one, and two children while preserving the ordering invariant.

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.

type SearchNode struct { Key int; Left,Right *SearchNode }
root := &SearchNode{Key: 4}
fmt.Println(root.Left == nil)

Insertion order can turn the tree into a chain

A two-child deletion usually substitutes the in-order successor and then removes that successor from its original position. Merely clearing one link can lose an entire subtree. A plain BST is not automatically balanced; sorted insertion can make it a chain. The tagged result struct replaces a dynamically mixed result list while keeping boolean values distinct from optional integer floors.

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.

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