hardTreesPure DSA~40 min
Repair A BST With Two Swapped Nodes
A pricing tree stored as a binary search tree got corrupted: exactly two node values were swapped by mistake. Restore the BST by swapping them back, without changing the tree's structure.
Problem
Given the root of a binary search tree where exactly two nodes had their values swapped, recover the tree so it is a valid BST again. Do it in place; an O(1)-space (Morris traversal) solution is preferred but O(h) is acceptable.
Input
The root of a binary tree (a BST with two values swapped).
Output
The same tree with the two swapped values corrected.
Constraints
- 1 ≤ node count ≤ 1e4
- -2^31 ≤ node value ≤ 2^31 - 1
Examples
Example 1
Input
[1,3,null,null,2]
Output
[3,1,null,null,2]
Nodes 1 and 3 were swapped; swapping back yields a valid BST.
Example 2
Input
[3,1,4,null,null,2]
Output
[2,1,4,null,null,3]
Nodes 2 and 3 were swapped.