Binary Trie & XOR Linear Basis — Greedy Opposite-Bit Walk

Insert numbers MSB-first into a 0/1 trie, then watch a query walk down choosing the opposite bit to maximize XOR. Switch modes to build the linear basis by reducing each value.

step 0

Binary trie (MSB-first, B = 5)

query path chosen (opposite) edge trie node

Query progress

partner being traced (best y so far):
XOR so far (x ^ y):
Press Step to begin the greedy walk.
We insert each number into the trie from the most-significant bit down. Then a query value walks the trie, always trying to take the bit opposite to its own to make the XOR as large as possible.
Self-contained visualization. The trie answers max XOR of the query against the stored set (a pair question); the basis answers max XOR of any subset. See junior.md and professional.md for the proof that the greedy opposite-bit walk is optimal (most-significant differing bit dominates).