# Recover Binary Search Tree LeetCode Solution | Easy Approach

Share:

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?

Time: O(n)
Space: O(h)

### C++

``````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)
return;

inorder(root->left);

if (pred && root->val < pred->val) {
y = root;
if (!x)
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;
}
};``````

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

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

#### Watch Tutorial

Checkout more Solutions here