# Recover Binary Search Tree Problem Solution

Recover Binary Search Tree 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.

```Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]```

## Problem Solution In Python

``````class Solution:
def recoverTree(self, root: TreeNode) -> None:
self.first, self.second, self.prev = None, None, TreeNode(float('-inf'))

def inorder(node):
if node:
inorder(node.left)
if self.prev.val >= node.val:
if not self.first:
self.first = self.prev
self.second = node
self.prev = node
inorder(node.right)

inorder(root)
self.first.val, self.second.val = self.second.val, self.first.val
``````

## Problem Solution In Java

``````class Solution {
ArrayList<Integer> list=new ArrayList<Integer>();
int count=0;
public void InOrder(TreeNode root)
{
if(root!=null)
{
InOrder(root.left);
if(list.get(count)!=root.val)
{
root.val=list.get(count);
}
count++;
InOrder(root.right);
}
}
public void recoverTree(TreeNode root)
{
Stack<TreeNode> stck=new Stack<TreeNode>();
int flag=0;
TreeNode current=root;
while(flag!=1)
{
if(current!=null)
{
stck.push(current);
current=current.left;
}
else
{
if(stck.empty())
{
flag=1;
}
else
{
current=stck.pop();
current=current.right;
}
}
}

Collections.sort(list);
InOrder(root);
}
}
``````

## Problem Solution In C++

``````class Solution {
public:

void fun(TreeNode* root, TreeNode*&first, TreeNode*&mid, TreeNode*&last, TreeNode*&prev)
{
if(!root)
return;
fun(root->left,first,mid,last,prev);
if(prev && root->val <prev->val)
{
if(!first)
{
first = prev;
mid = root;
}
else last = root;
}
prev = root;
fun(root->right,first,mid,last,prev);
}

void recoverTree(TreeNode* root){
if(!root)
return ;
TreeNode* first = NULL, *last = NULL, *mid = NULL, *prev = NULL;
fun(root,first,mid,last,prev);
if(last)
swap(last->val,first->val);

else swap(first->val,mid->val);
}
};
``````

## Problem Solution In C

``````void recoverTree_r(struct TreeNode* root, struct TreeNode** fNode,
struct TreeNode** sNode, struct TreeNode** pNode){

if(root == NULL)
return;

recoverTree_r(root->left, fNode, sNode, pNode);

if(*pNode == NULL)
*pNode = root;

if((*pNode)->val > root->val) {
if(*fNode == NULL)
*fNode = *pNode;
*sNode = root;
}
*pNode = root;

recoverTree_r(root->right, fNode, sNode, pNode);

}
void recoverTree(struct TreeNode* root){
struct TreeNode* fNode = NULL, *sNode = NULL, *pNode = NULL;
recoverTree_r(root, &fNode, &sNode, &pNode);
int t = fNode->val;
fNode->val = sNode->val;
sNode->val = t;
return;
}``````

If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.