Recover Binary Search Tree

I rejected a candidate on this exact problem because their solution sorted the in-order traversal and rebuilt the tree, which technically works but completely misses the point. The interview signal here is whether you spot that an in-order traversal of a BST should be strictly sorted, so any inversion (descent) in that sequence is a corrupted node, and the two corrupted nodes are exactly the ones that need swapping. Once that clicks, the algorithm is half a screen of code.

Recover Binary Search Tree

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Examples

Example 1:

• Input: root = [1, 3, null, null, 2]
• Output: [3, 1, null, null, 2]
• Explanation: In the broken tree, in-order traversal yields 1, 3, 2 (a descent at 3 -> 2). The values 1 and 3 were swapped. After recovery, in-order is 1, 2, 3.

Example 2:

• Input: root = [3, 1, 4, null, null, 2]
• Output: [2, 1, 4, null, null, 3]
• Explanation: In-order is 1, 3, 2, 4. The descents reveal that 3 and 2 were swapped. Swapping back gives 1, 2, 3, 4.

Example 3:

• Input: root = [2, 3, 1]
• Output: [2, 1, 3]
• Explanation: In-order is 3, 2, 1 with descents at 3 -> 2 and 2 -> 1. The two outermost values, 3 and 1, are the swap.

Example 4:

• Input: root = [3, 2, 1] (already sorted in-order: 1, 2, 3)
• This case never appears under the problem's guarantee, but the algorithm correctly returns the same tree if it is run on a valid BST.

Constraints

• The number of nodes in the tree is in the range [2, 1000].
• -2^31 <= Node.val <= 2^31 - 1.
• The tree is a valid BST except for exactly one swapped pair of values.

Follow-up

A solution using O(n) space is straightforward (write down the in-order, find the descent, swap). Can you devise a constant-space solution? An O(h) recursion-stack version is the natural answer; Morris traversal gives true O(1) extra space.