Replace suspended recursive calls by an explicit stack for an inorder traversal. Save each original right child before overwriting that link:The method belongs to the concrete class owning
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)
}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 time complexity and 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.[ref] Articles by others on the same topic
There are currently no matching articles.