# Recover Binary Search Tree Leetcode Solution

In this post, we are going to solve the Recover Binary Search Tree Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

## 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`

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

Now, lets see the leetcode solution of Recover Binary Search Tree Leetcode Solution.

### Recover Binary Search Tree Leetcode Solution in Python

```class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
def swap(x: Optional[TreeNode], y: Optional[TreeNode]) -> None:
temp = x.val
x.val = y.val
y.val = temp

def inorder(root: Optional[TreeNode]) -> None:
if not root:
return

inorder(root.left)

if self.pred and root.val < self.pred.val:
self.y = root
if not self.x:
self.x = self.pred
else:
return
self.pred = root

inorder(root.right)

inorder(root)
swap(self.x, self.y)

pred = None
x = None  # 1st wrong node
y = None  # 2nd wrong node
```

### Recover Binary Search Tree Leetcode Solutionin CPP

```class Solution {
public:
void recoverTree(TreeNode* root) {
inorder(root);
swap(x, y);
}

private:
TreeNode* pred = nullptr;
TreeNode* x = nullptr;  // 1st wrong node
TreeNode* y = nullptr;  // 2nd wrond node

void inorder(TreeNode* root) {
if (root == nullptr)
return;

inorder(root->left);

if (pred && root->val < pred->val) {
y = root;
if (x == nullptr)
x = pred;
else
return;
}
pred = root;

inorder(root->right);
}

void swap(TreeNode* x, TreeNode* y) {
const int temp = x->val;
x->val = y->val;
y->val = temp;
}
};
```

### Recover Binary Search Tree Leetcode Solution in Java

```class Solution {
public void recoverTree(TreeNode root) {
inorder(root);
swap(x, y);
}

private TreeNode pred = null;
private TreeNode x = null;
private TreeNode y = null;

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

inorder(root.left);

if (pred != null && root.val < pred.val) {
y = root;
if (x == null)
x = pred;
else
return;
}
pred = root;

inorder(root.right);
}

private void swap(TreeNode x, TreeNode y) {
final int temp = x.val;
x.val = y.val;
y.val = temp;
}
}
```

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

Sharing Is Caring