Flatten Solution

The iterative approach processes in preorder without extra space:

function flatten(root):
    current = root
    while current:
        if current.left:
            // Find rightmost node of left subtree
            rightmost = current.left
            while rightmost.right:
                rightmost = rightmost.right
            // Rewire: rightmost.right = current.right
            rightmost.right = current.right
            // Move left subtree to right
            current.right = current.left
            current.left = null
        current = current.right

The idea: before going right, splice the entire left subtree between current and current.right. The rightmost node of the left subtree connects to what was current.right.

Time: $O(n)$. Space: $O(1)$.