= Solution
Allocate nodes only as required, explicitly initializing every field:
``
PROCEDURE Make(VAR t: Trie);
VAR c: INTEGER;
BEGIN
NEW(t); t.terminal := FALSE; c := 0;
WHILE c < 26 DO t.child[c] := NIL; c := c+1 END
END Make;
PROCEDURE AddTail(VAR t: Trie; s: ARRAY OF CHAR; i: INTEGER);
BEGIN
IF t = NIL THEN Make(t) END;
IF s[i] = 0X THEN
t.terminal := TRUE
ELSE
AddTail(t.child[Index(s[i])], s, i+1)
END
END AddTail;
PROCEDURE Add(VAR t: Trie; s: ARRAY OF CHAR);
BEGIN
AddTail(t, s, 0)
END Add;
``
Here `0X` is the zero character, and `s` must contain its terminator within its <array> bounds. `Make` establishes that the first `c` child fields are `NIL` as its <loop invariant>. Passing `t` by reference lets the base allocation replace a missing root or child pointer.
For correctness, use <induction> on the number of characters before the terminator. At length zero, setting `terminal` adds exactly the empty suffix. Otherwise the chosen child stores exactly words with the required next letter, and the <induction hypothesis> adds the remaining suffix while preserving all other words. Thus \b[the resulting <set> is the old <set> union the supplied word, ignoring case]. Repeated insertion changes no word membership. A newly allocated path reaches the newly terminal node, preserving the canonical <representation invariant> after the procedure finishes. The <running time> is $O(1+\ell)$ for a word of length $\ell$, using $O(1+\ell)$ <call stack> space without optimization.
Back to article page
