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


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.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment