Numerically largest entry in a trie of digits

[Steven Schveighoffer]

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