= Solution
Push the right child before the left child so that the <LIFO stack> exposes the left child first:
``
def preorderIterative(t: Tree): Unit = {
val pending = new Stack
if (t != null) pending.push(t)
while (!pending.isEmpty) {
val u = pending.pop
println(u.datum)
if (u.right != null) pending.push(u.right)
if (u.left != null) pending.push(u.left)
}
}
``
Let $P(u)$ be the <sequence> of labels in the <preorder traversal> of $u$. If the abstract pending <stack>, top first, is $[u_1,\ldots,u_k]$, the <loop invariant> is that the output already printed, followed by $P(u_1)\mathbin{+\!+}\cdots\mathbin{+\!+}P(u_k)$, is the required full output. Each pending root is non-null, and its <subtree> is still unvisited. This is the pending-work form of <explicit-stack depth-first tree traversal>.
One iteration discharges the first root's own label and replaces its remaining obligation by the left <subtree> followed by the right <subtree>. The push order makes that precisely the new top-first pending order. Thus the <loop invariant> is preserved. The <loop variant> is the sum of the numbers of <vertices> in all pending <subtrees>; it decreases by exactly one per iteration, even if the number of <stack> entries increases. When the <stack> is empty there is no remaining output obligation, proving correctness and termination. This assumes a finite genuine <binary tree> and, as permitted, sufficient <stack> capacity. Each <vertex> is pushed and popped once, giving \b[$\Theta(n)$ time] and $O(h+1)$ pending references for <binary tree> height $h$.
Back to article page
