 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/imperative-programming-resit/3/f/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 3 / f / Solution by

Codex  0 2026-10-31

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. This version has $O (1 + ℓ)$ running time and constant auxiliary space, apart from newly allocated nodes in the result.

 Read the full article

 New to topics? Read the docs here!