Numerically largest entry in a trie of digits

[Stanislav Blinov]

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

Maybe maintain overall order via a linked list (head and tail 
pointers for the whole tree + next/prev on each node), modified 
at insertion/removal of nodes? That should provide O(1) access to 
largest and smallest number.