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();
                    list.add(current.val);
                    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;
}