# Recover Binary Search Tree – Leetcode Solution

In this post, we are going to solve the 99. Recover Binary Search Tree problem of Leetcode. This problem 99. Recover Binary Search Tree is a Leetcode medium level problem. Let’s see the code, 99. Recover Binary Search Tree – Leetcode Solution.

## Problem

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]`.
• `-231 <= Node.val <= 231 - 1`

Now, let’s see the code of 99. Recover Binary Search Tree – Leetcode Solution.

# Recover Binary Search Tree – Leetcode Solution

### 99. Recover Binary Search Tree – Solution in Java

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/

class Solution {

private TreeNode first;
private TreeNode second;
private TreeNode prev;

public void recoverTree(TreeNode root) {
if(root==null) return;

first = null;
second = null;
prev = null;

inorder(root);

int temp = first.val;
first.val = second.val;
second.val = temp;
}

private void inorder(TreeNode root){
if(root==null) return;
inorder(root.left);

if(first==null && (prev != null && prev.val>=root.val)){
first = prev;
}
if(first!=null && prev.val>=root.val){
second = root;
}
prev = root;
inorder(root.right);
}
}
```

### 99. Recover Binary Search Tree – Solution in C++

```/**
* 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 {
TreeNode* first, *last, *prev;
public:
void inorder(TreeNode* root){
if(root==NULL) return;
inorder(root->left);
if(prev!=NULL && (root->val<prev->val)){
if(first==NULL){
first=prev;
last=root;
}
else
last=root;
}
prev=root;
inorder(root->right);
}
void recoverTree(TreeNode* root) {
first=last=prev=NULL;
inorder(root);
swap(first->val,last->val);
}
};```

### 99. Recover Binary Search Tree– Solution in Python

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def recoverTree(self, root): # O(lg(n)) space
pre = first = second = None
stack = []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
break
node = stack.pop()
if not first and pre and pre.val > node.val:
first = pre
if first and pre and pre.val > node.val:
second = node
pre = node
root = node.right
first.val, second.val = second.val, first.val
```

Note: This problem 99. Recover Binary Search Tree is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.