99. Recover Binary Search Tree

Question

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were 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]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Constraints:

• The number of nodes in the tree is in the range [2, 1000].
• -2^31 <= Node.val <= 2^31 - 1

Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?

---

Approach

1. Traverse to the left most node.
2. Store the left most node as prevNode, this is the node that we will be using for comparision.
3. Perform in-order traversal, when the value of prevNode is greater than the value of the current node, and
   • If we have previously found another wrongly arranged node, and that node is greater than current node, we will update the 1st node to swap as the current node.
   • Else, update the 1st node to swap as the current node, and the 2nd node to swap as the previous node.
4. After the in-order is complete, swap the values of 2 nodes.

Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* prevNode = NULL;
    TreeNode* toSwap1 = NULL;
    TreeNode* toSwap2 = NULL;
    
    void recoverTree(TreeNode* root) {
        //Travers in-order
        inOrder(root);
        
        //Swap values of wrongly arrange nodes
        int tmp =toSwap1->val;
        toSwap1->val = toSwap2->val;
        toSwap2->val = tmp;
    }
    
    void inOrder(TreeNode* root) {
        if(root == NULL) return;
        inOrder (root->left);
        
        //Only enter from second smallest node onwards so we can compare
        //If the previous node value is larger than current value (violates BST)
        if(prevNode != NULL && prevNode->val > root->val){
            //Only enter if one node is already found to be wrongly arranged
            //If that node is larger than the current node
            if(toSwap2 != NULL && toSwap2->val > root->val){
                //we swap this node and the previous found node instead
                toSwap1 = root;
            }else{
                //otherwise we swap with the previous node
                toSwap1 = root;
                toSwap2 = prevNode; 
            }
        }
        
        //store the previous node during traversal
        prevNode = root;
        inOrder (root->right);
    }
};