start == null if and only if end == null. Otherwise there is a finite list of distinct software objects , with start eq v0, end eq v(m-1), v0.left == null, and v(m-1).right == null. For every valid adjacent pair, v(i).right eq v(i+1) and v(i+1).left eq v(i). These are exactly the entries reachable through the list links, so there is no extra cycle or branch. All counts are positive, all words are non-null, and words strictly increase from start to end.This is the representation invariant for a null-terminated doubly linked list without a list header. The abstraction function reads the ordered word-count pairs from left to right. Conversion additionally requires the output entries, counts and words to be precisely those of the input binary search tree; that preservation property is an operation postcondition, rather than an invariant of an arbitrary list by itself.
Perform a destructive binary search tree flattening by converting both child subtrees and splicing their endpoints around the original root:Save the child references before changing their interpretation. The input is a finite binary search tree satisfying part (b), and no external client may simultaneously rely on the old tree links. By structural induction, the two recursive calls return disjoint, ordered doubly linked lists containing exactly their original entries. The binary search tree bounds place every left word before
def flatten(t: Tree): (Tree, Tree) = {
if (t == null) (null, null)
else {
val oldLeft = t.left
val oldRight = t.right
val (ls, le) = flatten(oldLeft)
val (rs, re) = flatten(oldRight)
t.left = le
if (le != null) le.right = t
t.right = rs
if (rs != null) rs.left = t
val start = if (ls == null) t else ls
val end = if (re == null) t else re
(start, end)
}
}t.word and every right word after it. Splicing the left end, t, and the right start therefore preserves strict order and reciprocal links. A missing left list makes t.left null and t the start; a missing right list similarly makes t the end. The resulting outside links are null as required by part (i).The recursive loop variant analogue is the strictly smaller number of entries in each child subtree. Every entry is processed once and incurs a constant number of link writes, so time complexity is and recursion uses auxiliary space. No new
Tree entry is created; returning endpoint tuples and using a call stack are permitted auxiliary storage. The old binary search tree representation is consumed by this operation.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.