Recover Binary Search Tree - Leetcode Solution

The Recover Binary Search Tree problem on LeetCode asks us to recover a binary search tree where two of its nodes have been swapped. The problem can be divided into three major steps:

Step 1: Identify the two swapped nodes Step 2: Swap the two nodes to recover the original tree Step 3: Return the recovered tree

Step 1 - Identify the two swapped nodes:

To identify the two swapped nodes, we need to traverse through the tree and find the first node that is greater than its next node. This is because in a binary search tree, the value of the left node is always less than the value of the right node.

Once we have found the first node, we need to traverse the rest of the tree and find the node that is less than the original node. We swap these two nodes.

Here is the code snippet for step 1:

TreeNode* firstNode = NULL; TreeNode* secondNode = NULL; TreeNode* prevNode = new TreeNode(INT_MIN);

void findSwappedNodes(TreeNode* root){ if(root == NULL) return;

findSwappedNodes(root->left);

if(firstNode == NULL && prevNode->val >= root->val)
    firstNode = prevNode;

if(firstNode != NULL && prevNode->val >= root->val)
    secondNode = root;

prevNode = root;

findSwappedNodes(root->right);

}

findSwappedNodes(root);

Step 2 - Swap the two nodes to recover the original tree:

Once we have identified the two swapped nodes, we need to swap their values to recover the original tree.

Here is the code snippet for step 2:

int temp = firstNode->val; firstNode->val = secondNode->val; secondNode->val = temp;

Step 3 - Return the recovered tree:

After swapping the nodes, we can return the recovered tree.

Here is the code snippet for step 3:

return root;

Putting it all together, the complete solution for the Recover Binary Search Tree problem on LeetCode looks like this:

class Solution { public: TreeNode* recoverTree(TreeNode* root) { TreeNode* firstNode = NULL; TreeNode* secondNode = NULL; TreeNode* prevNode = new TreeNode(INT_MIN);

    void findSwappedNodes(TreeNode* root){
        if(root == NULL)
            return;

        findSwappedNodes(root->left);

        if(firstNode == NULL && prevNode->val >= root->val)
            firstNode = prevNode;

        if(firstNode != NULL && prevNode->val >= root->val)
            secondNode = root;

        prevNode = root;

        findSwappedNodes(root->right);
    }

    findSwappedNodes(root);

    int temp = firstNode->val;
    firstNode->val = secondNode->val;
    secondNode->val = temp;

    return root;
}

};

1