323. Correct BST with two nodes swapped

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.

Now Your Turn!

Pick the correct output for the given input

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

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= Number of Nodes <= 104
  • -231 <= Node.val <= 231 - 1

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
 
class Solution {
public:
void recoverTree(TreeNode* root) {
//your code goes here
}
};
Test Case

Input:

Root
to save your code