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.