Last updated on October 10th, 2024 at 12:28 am

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

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

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

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

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

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