Recover Binary Search Tree

Two nodes of the BST are swapped by mistake. Recover the tree without changing its structure.

Example 1

Input: root=[1,3,null,null,2] → Output: [3,1,null,null,2]

Example 2

Input: root=[3,1,4,null,null,2] → Output: [2,1,4,null,null,3]

Solution Approach

Inorder traversal of BST should give sorted sequence. Find two nodes where order is violated: first is the node where nums[i] > nums[i+1] for the first time, second is the smaller of the violating pair or the last violation.

Do inorder traversal, tracking prev node.
When prev.val > cur.val: if first==null, first=prev; second=cur.
After traversal, swap first.val and second.val.

Java

class Solution {
    TreeNode first, second, prev;
    public void recoverTree(TreeNode root) {
        inorder(root);
        int tmp = first.val; first.val = second.val; second.val = tmp;
    }
    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        if (prev != null && prev.val > node.val) {
            if (first == null) first = prev;
            second = node;
        }
        prev = node;
        inorder(node.right);
    }
}

Time Complexity: O(N)
Space Complexity: O(H)