= Solution
Use an explicit <stack> of handles. Push the right <subtree> first, so that the left <subtree> is removed first by the <LIFO stack>.
``
PROCEDURE PreorderIter(t: Tree; VAR out: ARRAY OF INTEGER;
VAR count: INTEGER;
VAR stack: ARRAY OF Tree);
VAR top: INTEGER; p: Tree;
BEGIN
count := 0; top := 1; stack[0] := t;
WHILE top > 0 DO
DEC(top); p := stack[top];
IF p = 0 THEN
out[count] := 0; INC(count)
ELSE
out[count] := 1; INC(count);
stack[top] := nodes[p-1].right; INC(top);
stack[top] := nodes[p-1].left; INC(top)
END
END
END PreorderIter;
``
The <loop invariant> says that the already written prefix, followed by the <preorder traversals> of the pending <subtrees> in top-to-bottom <stack> order, equals the entire required output. Popping a <leaf of a rooted tree> transfers one marker to the prefix. Popping a fork transfers its marker and replaces its remaining work by left then right <subtree> work. Both preserve the <loop invariant>. The number of as-yet-unwritten <vertices> decreases by one per iteration, proving termination.
$$
\boxed{\text{Push right, push left; pop and emit until the stack is empty.}}
$$
The <time complexity> is linear in the output length. The maximum <stack> size is at most one plus the <height of a binary tree>.
Back to article page
