# Recover Binary Search Tree

The items in a binary search tree are distinct and sorted in ascending order with in-order traversal. So, if two elements a exchanged, there will be two exception in the ascending order. Those two items are what we want to find.

Note the first exception will be a node has higher value than is descender and the section exception will be a node has lower value than its ascender. These two exception may be adjoined items in the in-order traversal.

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

class Res {
int next = Integer.MIN_VALUE;
TreeNode a;
TreeNode b;
}

public class RecoverBinarySearchTree {
private void findWrongNodes(TreeNode root, Res res) {
if (root == null) return;

findWrongNodes(root.left, res);
if (res.next > root.val) {
res.b = root;
}

res.next = root.val;
if (res.b == null) res.a = root;

findWrongNodes(root.right, res);
}

public void recoverTree(TreeNode root) {
Res res = new Res();
findWrongNodes(root, res);

if (res.a != null && res.b != null) {
int val = res.a.val;
res.a.val = res.b.val;
res.b.val = val;
}
}
}