# Recover Binary Search Tree LeetCode Solution

Here, We see Recover Binary Search Tree LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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

## Recover Binary Search Tree Leetcode Solution C++

``````class Solution {
private:

void markTree(TreeNode* root, TreeNode*& prev, TreeNode*& first, TreeNode*& end) {
if (!root) return;
markTree(root->left, prev, first, end);
if (prev) {
if (root->val < prev->val) {
if (!first) {
first = prev;
}
end = root;
}
}
prev = root;
markTree(root->right, prev, first, end);
}

public:
void recoverTree(TreeNode* root) {
TreeNode *prev = nullptr, *first = nullptr, *end = nullptr;
markTree(root, prev, first, end);
swap(first->val, end->val);
return;
}
};```Code language: PHP (php)```

## Recover Binary Search Tree Leetcode Solution Java

``````class Solution {
public void recoverTree(TreeNode root) {
TreeNode first = null;
TreeNode second = null;
TreeNode prev = null;
boolean swaped = false;
while(root!=null){
if(root.left==null){
if(prev!=null){
if(root.val<prev.val){
if(first==null){
first = prev;
second = root;
}else{
swap(first,root);
swaped = true;
}
}
}
prev = root;
root = root.right;
}else{
TreeNode cur = root;
TreeNode left = root.left;
while(left.right!=null&&left.right!=cur){
left = left.right;
}
if(left.right==null){
left.right = cur;
root = root.left;
}else{
if(prev!=null){
if(root.val<prev.val){
if(first==null){
first  = prev;
second = root;
}else{
swap(first,root);
swaped = true;
}
}
}
left.right = null;
prev = root;
root = root.right;
}
}
}
if(!swaped){
swap(first,second);
}
}
public void swap(TreeNode a,TreeNode b){
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
}```Code language: JavaScript (javascript)```

## Recover Binary Search Tree Leetcode Solution JavaScript

``````var recoverTree = function(root) {
let first = null;
let last = null;
let prev = null;

function dfs (node) {
if (!node) return;

dfs (node.left);

if (prev && node.val < prev.val){
if (first === null) first = prev;

last = node;
}
prev = node;

dfs (node.right);
}
dfs(root, null)

let temp = first.val;
first.val = last.val;
last.val = temp

return root;
};```Code language: JavaScript (javascript)```

## Recover Binary Search Tree Leetcode Solution Python

``````class Solution(object):
def recoverTree(self, root):
x, y = self.forward(root, []), self.backward(root, [])
x.val, y.val = y.val, x.val
return root

def forward(self, root, n):
if root is None:
return

ret = self.forward(root.left, n)
if ret:
return ret

if not n:
n.append(root)
elif root.val < n[0].val:
return n[0]
else:
n[0] = root

ret = self.forward(root.right, n)
if ret:
return ret

def backward(self, root, n):
if root is None:
return

ret = self.backward(root.right, n)
if ret:
return ret

if not n:
n.append(root)
elif root.val > n[0].val:
return n[0]
else:
n[0] = root

ret = self.backward(root.left, n)
if ret:
return ret```Code language: HTML, XML (xml)```
Scroll to Top