Numerically largest entry in a trie of digits

[Alexandru Ermicioi]

On Tuesday, 19 April 2022 at 16:35:21 UTC, 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?
>
>
> T

Perhaps have each node children sorted first by:
- having themselves a child
- digit itself

Then rightmost/leftmost chain of nodes should give what you want.

Alexandru.