= Destructive binary search tree flattening
Turn a <binary search tree> into a sorted <doubly linked list> by reusing each <linked list node>'s left and right child fields as predecessor and successor fields. An <inorder traversal> determines the required order. A recursive implementation first saves both child references, flattens the disjoint child <subtrees>, and splices their endpoints around the root. <Structural induction> proves that it preserves every original entry exactly once and produces reciprocal links with null outside endpoints. An explicit <stack> implements the same traversal without <recursive calls>; each original right child must be saved before its field is overwritten. Both versions take linear <time complexity> and $O(h+1)$ <auxiliary space> for original height $h$. The old <binary search tree> representation is consumed, so outside aliases must not continue to interpret the changed links as child pointers.
Back to article page
