= Solution
Replace suspended <recursive calls> by an explicit <stack> for an <inorder traversal>. Save each original right child before overwriting that link:
``
def flattenIterative(): (Tree, Tree) = {
val pending = new scala.collection.mutable.Stack[Tree]
var current = root
var start: Tree = null
var end: Tree = null
while (current != null || pending.nonEmpty) {
while (current != null) {
pending.push(current)
current = current.left
}
val t = pending.pop()
val nextSubtree = t.right
t.left = end
if (end == null) start = t else end.right = t
t.right = null
end = t
current = nextSubtree
}
root = null
(start, end)
}
``
The method belongs to the concrete class owning `root`. Clearing `root` records that ownership has transferred to the returned <doubly linked list>; callers retain both returned endpoints. The inner <loop invariant> says that the current <subtree> lies before all its pending ancestors in <inorder traversal>; pushing and descending left preserves this fact. Its <loop variant> is the number of entries along the remaining left-child path, a finite decreasing quantity.
The outer <loop invariant> says that `start` through `end` is precisely the already emitted sorted prefix, with reciprocal links and null outside endpoints. `current` and the pending ancestors describe exactly the remaining traversal in order; original links that are still needed have been retained. A pending ancestor has not yet had its right child overwritten. The next popped entry is therefore the next sorted entry. Saving `nextSubtree` preserves its future work before assigning `t.right = null`; linking it to `end` extends the prefix by exactly one entry. The number of original entries not yet emitted is an outer <loop variant>, since each full outer iteration emits one. At exit nothing remains, proving the same preservation and ordering <postconditions> as the recursive version.
Each entry is pushed and popped once, giving $O(n+1)$ <time complexity> and $O(h+1)$ <auxiliary space>. No new `Tree` entries are allocated. The historical mutable <stack> interface provides the `push` and `pop` operations used here; its later deprecation does not change their meaning.<Scala 2.12 mutable Stack API documentation>[Scala 2.12.6, constructors, push(elem), pop(), nonEmpty]{ref}
Back to article page
