# Recover Binary Search Tree

This is No.99 in LeetCode.

Here are approaches to this problem:

##### Algorithm

Here is the algorithm:

1. Construct inorder traversal of the tree. It should be an almost sorted list where only two elements are swapped.

2. Identify two swapped elements x and y in an almost sorted array in linear time.

3. Traverse the tree again. Change value x to y and value y to x.

``````class Solution {
public void inorder(TreeNode root, List<Integer> nums) {
if (root == null) return;
inorder(root.left, nums);
inorder(root.right, nums);
}

public int[] findTwoSwapped(List<Integer> nums) {
int n = nums.size();
int x = -1, y = -1;
for(int i = 0; i < n - 1; ++i) {
if (nums.get(i + 1) < nums.get(i)) {
y = nums.get(i + 1);
// first swap occurence
if (x == -1) x = nums.get(i);
// second swap occurence
else break;
}
}
return new int[]{x, y};
}

public void recover(TreeNode r, int count, int x, int y) {
if (r != null) {
if (r.val == x || r.val == y) {
r.val = r.val == x ? y : x;
if (--count == 0) return;
}
recover(r.left, count, x, y);
recover(r.right, count, x, y);
}
}

public void recoverTree(TreeNode root) {
List<Integer> nums = new ArrayList();
inorder(root, nums);
int[] swapped = findTwoSwapped(nums);
recover(root, 2, swapped[0], swapped[1]);
}
}``````
##### Approach 2: Iterative Inorder Traversal
``````class Solution {
public void swap(TreeNode a, TreeNode b) {
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}

public void recoverTree(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque();
TreeNode x = null, y = null, pred = null;

while (!stack.isEmpty() || root != null) {
while (root != null) {
root = root.left;
}
root = stack.removeLast();
if (pred != null && root.val < pred.val) {
y = root;
if (x == null) x = pred;
else break;
}
pred = root;
root = root.right;
}

swap(x, y);
}
}``````
##### Approach 3: Recursive Inorder Traversal

This is recursion version of approach 2.

``````class Solution {
TreeNode x = null, y = null, pred = null;

public void swap(TreeNode a, TreeNode b) {
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}

public void findTwoSwapped(TreeNode root) {
if (root == null) return;
findTwoSwapped(root.left);
if (pred != null && root.val < pred.val) {
y = root;
if (x == null) x = pred;
else return;
}
pred = root;
findTwoSwapped(root.right);
}

public void recoverTree(TreeNode root) {
findTwoSwapped(root);
swap(x, y);
}
}``````