# Recover Binary Search Tree Problem

## Description

LeetCode Problem 99.

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:

``````1
2
3
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:

``````1
2
3
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

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
TreeNode* first=NULL;
TreeNode* second=NULL;
TreeNode* prev = new TreeNode(INT_MIN);
public:
void recoverTree(TreeNode* root) {
help(root);
swp(first->val, second->val);
}

void help(TreeNode* root){
if(root==NULL)  return;
help(root->left);
if(first==NULL && prev->val >= root->val)   first=prev;
if(first!=NULL && prev->val >= root->val)   second=root;
prev=root;
help(root->right);
}
};
``````