Recover BST Solution

Implement BST recovery using inorder traversal to find violations. Here's the trick: always set second = current when you find a violation.

For adjacent swaps, first and second are the same pair you found at the first violation.

For non-adjacent swaps, first is from the first violation and second is from the second. For $O(1)$ space: use Morris traversal.

Morris traversal modifies tree temporarily to traverse without a stack, then restores the structure. Time: $O(n)$. Space: $O(h)$ with recursion, $O(1)$ with Morris.