= Solution
Perform a <destructive binary search tree flattening> by converting both child <subtrees> and splicing their endpoints around the original root:
``
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)
}
}
``
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 `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 $O(n+1)$ and recursion uses $O(h+1)$ <auxiliary space>. \b[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.
Back to article page
