トライのイテレータを実装する必要があります。私が持っているとしましょう
a
/\
b c
/\
d e
現在のiterator.state="abd"の場合、iterator.next.state = "abe"、次に"ac"が必要です。各レベルで、ノードは辞書式順序でソートされます（たとえば、レベル2では、c後に続きbます）。また、これはlog（n）時間で発生するはずです。ここで、nはノードの数です。
私が考えることができる1つの解決策は、各ブランチの高さが同じである特殊なケースを検討することです。私が思うに、かなりクールな実装は、「レベル」ごとにバランスの取れたツリーを維持することです。「abdの後に続く文字列」を尋ねると、bに配置すると、3番目のレベルに関連付けられたツリーで「b」よりも大きい最初の要素を検索して「abe」を指定できます。
ただし、ツリーを作成する必要があるため、これは実用的ではない可能性があります。
質問を正しく理解していれば、反復子の状態は現在の文字列であり、トライ内の現在の場所へのポインターである可能性があります。次に、次の要素に移動します。
現在の場所に兄弟がある場合は、そこに移動して、現在の文字列の最後の文字を現在の場所の文字に置き換えます。
それ以外の場合は、最後の文字を削除してツリーを上ります。ルートから上に行こうとしている場合は、完了です。それ以外の場合は、ステップ 1 に進みます。
たとえば、(あなたの例では) abd にいるとき、現在の文字列は "abd" であり、ポインタは 'd' を指しています。次の要素に移動するには、文字列を "ab" に変更し、兄弟ノード ('e') に移動して文字列に追加し、"abe" を生成します。その後、兄弟がないため上に移動し、次に b の兄弟に移動して、正しい次の値 'ac' を生成します。
ご覧のとおり、最悪の場合、これらの各ステップは、兄弟を見つける前にルートまで戻る必要があります。それがあなたが求めていたlog(n)です。