I need to implement an iterator for a trie. Let's say I have
a
/\
b c
/\
d e
If the current iterator.state="abd", I would like to have iterator.next.state="abe", then "ac". At each level, nodes are sorted in lexicographical order (e.g. on level 2, c comes after b). Also this should happen in log(n) time, where n is the number of nodes.
One solution I can think of is: consider a special case, when each branch has the same height. A rather cool implementation I think, would be to maintain a balanced tree for each "level". On asking: "what string follows after abd", when positioned on b, one could search for the first element bigger than "b" in the tree associated with the third level, giving "abe".
However that might be impractical, due to having to create the trees.
If I understand the question correctly, the iterator state could be the current string and a pointer to the current location in the trie. Then, to move to the next element:
if your current location has a sibling, move to it and replace the last character in the current string with the current location's character.
else, remove the last character and go up the tree. If you're trying to go up from the root, you're done. Otherwise, go to step 1.
So for example when you're at abd (in your example), the current string is "abd" and the pointer points to the 'd'. To move to the next element you change the string to "ab", move to the sibling node ('e') and add it to the string, yielding "abe". After that, you'll be going up since there's no sibling and then to b's sibling, yielding the correct next value 'ac'.
As you can see, at worst each of those steps needs to go all the way back to the root before it can find a sibling; that's the log(n) you were asking for.