= Solution
Perform a <depth-first traversal>, retaining the path's letters in a buffer. A terminal node must be printed before its children, so a word precedes its proper extensions in <lexicographic order>.
``
VAR word: ARRAY N OF CHAR;
PROCEDURE Visit(t: Trie; depth: INTEGER);
VAR j, c: INTEGER;
BEGIN
IF t # NIL THEN
IF t.terminal THEN
j := 0;
WHILE j < depth DO
Out.Char(word[j]); j := j+1
END;
Out.Ln
END;
c := 0;
WHILE c < 26 DO
IF t.child[c] # NIL THEN
word[depth] := CHR(ORD("a")+c);
Visit(t.child[c], depth+1)
END;
c := c+1
END
END
END Visit;
PROCEDURE PrintTrie(t: Trie);
BEGIN
Visit(t, 0)
END PrintTrie;
``
The <recursion invariant> is that `word[0..depth)` spells the path to `t`. The child loop's <loop invariant> says children with indices below `c` have been completely printed. Each edge appends its lowercase label; each terminal flag prints exactly one represented <string>. All words therefore appear once, in lowercase. The output loop prints precisely the prefix of length `depth`; no terminating zero needs storing in this buffer.
\b[An `N`-character buffer suffices for words of length at most `N`.] At depth `N` there can be no child, so `word[N]` is never accessed. A terminal root prints an empty line; a `NIL` root prints nothing. The <running time> is linear in allocated nodes plus the number of printed characters, since the alphabet size is fixed at 26.
Back to article page
