On 4/19/22 12:35 PM, H. S. Teoh wrote:
>Just thought I'd pick all the bright minds here: I have a set of numbers
in string form (as decimal digits), stored in a trie. How do I retrieve
the largest number in the set?
My initial guess was to find the rightmost child in the trie.
Unfortunately, this is incorrect, because the rightmost child may not
necessarily be the largest numerically. For example, consider the set
{1, 9, 10}. In trie form, 10 would be a child of 1 (it would be stored
as the digit path 1 -> 0), and the rightmost child would be 9, which is
less than 10.
It would appear that what I want is the rightmost longest entry in the
trie. Is there a more efficient way to compute this, short of
brute-force traversal over the entire trie?
Maybe store the longest chain in each node when inserting? Then you look for the longest chain first, and rightmost if there's more than one.
-Steve