99. Recover Binary Search Tree
Your function receives root, the root node of a binary search tree that has been sabotaged: the values of exactly two nodes were exchanged with each other. The shape of the tree is untouched and every value is distinct — only those two values sit in the wrong places.
Repair the tree in place by finding the two offending nodes and swapping their values back. The function returns nothing; do not rebuild or re-link the tree, and do not change any other node.
After your function runs, the judge prints the repaired tree in level order (existing nodes only), so a correct fix — and nothing else — must be visible in the structure you were handed.
Example 1:
Input: root = [1, 3, null, null, 2]
Output: [3, 1, null, null, 2]
Explanation: The values 1 and 3 were exchanged. Swapping them back yields the BST [3, 1, null, null, 2]; its nodes in level order read 3, 1, 2.
Example 2:
Input: root = [3, 1, 4, null, null, 2]
Output: [2, 1, 4, null, null, 3]
Explanation: The values 2 and 3 were exchanged. Restoring them gives [2, 1, 4, null, null, 3], printed in level order as 2, 1, 4, 3.
Constraints:
- 2 ≤ number of nodes ≤ 1000
- -10⁹ ≤ node value ≤ 10⁹
- All node values are distinct.
- The input is a valid BST in which the values of exactly two nodes have been exchanged.
Hints:
An inorder walk of a healthy BST lists values in strictly increasing order. What does that sequence look like after two values trade places — how many spots can 'descend' instead of rise?
If the swapped nodes are far apart the inorder sequence dips twice: the first bad pair's *left* element and the second bad pair's *right* element are the culprits. If they are inorder-neighbors there is only one dip — take both elements of that single pair. Track the previous node during one traversal and you never need to store the whole sequence.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 3, null, null, 2]
Expected output: [3, 1, null, null, 2]