= Solution
Let $L$ be the final output length, $k$ the number of emitted markers, and $s$ the number of pending handles. Each pending <subtree> contributes at least one future marker, so
$$
k+s\leq L\leq\operatorname{LEN}(\mathrm{out}).
$$
Store output from the low end and the <stack> from the high end of the same <array>. A pop frees one cell before the next write. For a fork, the two pushed children each account for at least one of the remaining markers. Thus the two regions never overlap.
``
PROCEDURE PreorderShared(t: Tree; VAR out: ARRAY OF INTEGER;
VAR count: INTEGER);
VAR top, cap: INTEGER; p: Tree;
BEGIN
cap := LEN(out); count := 0;
top := cap-1; out[top] := t;
WHILE top < cap DO
p := out[top]; INC(top);
IF p = 0 THEN
out[count] := 0; INC(count)
ELSE
out[count] := 1; INC(count);
DEC(top); out[top] := nodes[p-1].right;
DEC(top); out[top] := nodes[p-1].left
END
END
END PreorderShared;
``
The <loop invariant> includes `count <= top`, with pending handles in `out[top..cap)` and final markers in `out[0..count)`. The preceding accounting proves every intermediate write also respects <array bounds>. This uses the <integer> handle representation chosen in part (b). Simply putting a <pointer> into a genuinely <Boolean>-typed cell would not be valid <Oberon>.
$$
\boxed{\text{One result array suffices; additional working storage is }O(1).}
$$
Back to article page
