Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure, but by only swapping these two nodes.
Constraints:
- The number of nodes in the tree is in the range [1, 1000].
- 0 <= Node.val <= 1000
- Root is a valid binary search tree before swap.
Examples:
Input: [1, null, 2, null, null, 3, null, null, null, 4]
Output: [1, null, 2, null, null, 3, null, null, null, 4] after swapping node 2 and node 3
Explanation: The binary search tree is: 1 \ 2 \ 3 \ 4 After swapping node 2 and node 3, the binary search tree becomes: 1 \ 3 \ 2 \ 4
Solutions
Inorder traversal and swapping
The solution uses inorder traversal to find the two nodes that are in the wrong order. It keeps track of the previous node and checks if the current node's value is smaller than the previous node's value. If it is, it means that the current node and the previous node are the two nodes that need to be swapped.
var recoverTree = function (root) {
let prev = null,
big = null,
small = null;
function inorder(root) {
if (!root) return;
inorder(root.left);
if (prev && prev.val > root.val) {
small = root;
if (!big) big = prev;
}
prev = root;
inorder(root.right);
}
inorder(root);
[big.val, small.val] = [small.val, big.val];
};
Follow-up:
How would you solve this problem if you are not allowed to use any extra space?
