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;
        }
    }
}