Leetcode Recover Binary Search Tree problem solution

YASH PAL,

In this Leetcode Recover Binary Search Tree problem solution, we have given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Leetcode Recover Binary Search Tree problem solution

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

coding problems solutions