= Solution
`AddTail` in part (d) is already <tail-recursive>: the recursive call is the final action of its branch. The following loop follows a separate cursor so that the caller's root pointer is preserved:
``
PROCEDURE AddIter(VAR t: Trie; s: ARRAY OF CHAR);
VAR u: Trie; i, c: INTEGER;
BEGIN
IF t = NIL THEN Make(t) END;
u := t; i := 0;
WHILE s[i] # 0X DO
c := Index(s[i]);
IF u.child[c] = NIL THEN Make(u.child[c]) END;
u := u.child[c]; i := i+1
END;
u.terminal := TRUE
END AddIter;
``
The <loop invariant> is that `u` points to the node reached by the first `i` letters, all necessary nodes along that path exist, and no previously terminal node has lost its flag. Each iteration advances one character. At the terminator, marking `u` inserts exactly the desired <string>. Using `t := t.child[c]` as the cursor update would instead overwrite the caller's root through the `VAR` parameter. \b[This version has $O(1+\ell)$ <running time> and constant auxiliary space], apart from newly allocated nodes in the result.
Back to article page
