In this post, we are going to solve the Recover Binary Search Tree Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
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.
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.
Constraints:
- The number of nodes in the tree is in the range
[2, 1000]. -231 <= Node.val <= 231 - 1
Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?
Now, let’s see the leetcode solution of Recover Binary Search Tree Leetcode Solution.
Recover Binary Search Tree Leetcode Solution in Python
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
def swap(x: Optional[TreeNode], y: Optional[TreeNode]) -> None:
temp = x.val
x.val = y.val
y.val = temp
def inorder(root: Optional[TreeNode]) -> None:
if not root:
return
inorder(root.left)
if self.pred and root.val < self.pred.val:
self.y = root
if not self.x:
self.x = self.pred
else:
return
self.pred = root
inorder(root.right)
inorder(root)
swap(self.x, self.y)
pred = None
x = None # 1st wrong node
y = None # 2nd wrong node
Recover Binary Search Tree Leetcode Solution in CPP
class Solution {
public:
void recoverTree(TreeNode* root) {
inorder(root);
swap(x, y);
}
private:
TreeNode* pred = nullptr;
TreeNode* x = nullptr; // 1st wrong node
TreeNode* y = nullptr; // 2nd wrond node
void inorder(TreeNode* root) {
if (root == nullptr)
return;
inorder(root->left);
if (pred && root->val < pred->val) {
y = root;
if (x == nullptr)
x = pred;
else
return;
}
pred = root;
inorder(root->right);
}
void swap(TreeNode* x, TreeNode* y) {
const int temp = x->val;
x->val = y->val;
y->val = temp;
}
};
Recover Binary Search Tree Leetcode Solution in Java
class Solution {
public void recoverTree(TreeNode root) {
inorder(root);
swap(x, y);
}
private TreeNode pred = null;
private TreeNode x = null;
private TreeNode y = null;
private void inorder(TreeNode root) {
if (root == null)
return;
inorder(root.left);
if (pred != null && root.val < pred.val) {
y = root;
if (x == null)
x = pred;
else
return;
}
pred = root;
inorder(root.right);
}
private void swap(TreeNode x, TreeNode y) {
final int temp = x.val;
x.val = y.val;
y.val = temp;
}
}
Note: This problem Recover Binary Search Tree is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.
