= Solution
For parts (b)–(e), use <array indices> as <tree> handles. This also makes the shared storage in part (d) type-correct: both pending handles and output markers occupy <integer> cells. Zero denotes a <leaf of a rooted tree>; a positive handle $t$ denotes a fork whose children are in `nodes[t-1]`. Only finite acyclic structures are admitted. An allocated fork's children are themselves valid handles.
``
CONST MaxForks = 100000;
TYPE Tree = INTEGER;
Node = RECORD left, right: Tree END;
Arena = ARRAY MaxForks OF Node;
VAR nodes: Arena;
used: INTEGER;
PROCEDURE NewFork(left, right: Tree): Tree;
BEGIN
ASSERT(used < MaxForks);
nodes[used].left := left; nodes[used].right := right;
INC(used);
RETURN used
END NewFork;
PROCEDURE Preorder(t: Tree; VAR out: ARRAY OF INTEGER;
VAR count: INTEGER);
PROCEDURE Visit(p: Tree);
BEGIN
IF p = 0 THEN
out[count] := 0; INC(count)
ELSE
out[count] := 1; INC(count);
Visit(nodes[p-1].left); Visit(nodes[p-1].right)
END
END Visit;
BEGIN
count := 0; Visit(t)
END Preorder;
``
Initialize `used := 0` before constructing any <trees>; `NewFork` allocates within this arena. The fixed capacity is an implementation parameter and may be replaced by a dynamically allocated arena. The returned prefix `out[0..count)` encodes <Boolean> values by $0=\mathrm{False}$ and $1=\mathrm{True}$. This encoding is part of the chosen representation, not a conversion of a <pointer> into a <Boolean> value.
The <recursion invariant> is that `Visit(p)` appends exactly the <preorder traversal> of the <subtree> represented by `p`. If the <full binary tree> has $I$ forks, it has $I+1$ <leaf of a rooted tree>[leaves]; hence
$$
\boxed{\mathrm{count}=2I+1,\qquad \mathrm{out}[0..\mathrm{count})=P(t)\text{ encoded by }0,1.}
$$
Each occurrence is visited once, using linear <time complexity> and a <call stack> bounded by the <height of a binary tree>. The arena is the input representation, not an extra copy made by the traversal.
Back to article page
