In this post, you will know how 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.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.
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.
Recover Binary Search Tree Leetcode Solutions 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 Solutions 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 Solutions 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 Brokenprogrammers. This tutorial is only for Educational and Learning purposes.
Next: Validate Binary Search Tree Leetcode Solution
