Last updated on January 19th, 2025 at 10:45 pm
Here, we see a Recover Binary Search Tree LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Depth-First Search, Tree
Level of Question
Medium
Recover Binary Search Tree LeetCode Solution
Table of Contents
1. 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.
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Tree Depth First Search (DFS). The problem involves traversing a binary search tree (BST) to identify two nodes that are swapped and then recovering the tree by swapping their values back. The traversal is done using DFS (in-order traversal) to identify the misplaced nodes.
3. Code Implementation in Different Languages
3.1 Recover Binary Search Tree 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;
}
};
3.2 Recover Binary Search Tree 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.3 Recover Binary Search Tree 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;
};
3.4 Recover Binary Search Tree 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
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(h) |
| Java | O(n) | O(1) |
| JavaScript | O(n) | O(h) |
| Python | O(n) | O(h) |
where h is the height of the tree.
- Time Complexity:
- All implementations perform an in-order traversal of the tree, which visits each node exactly once. This results in a time complexity of O(n), where
nis the number of nodes in the tree.
- All implementations perform an in-order traversal of the tree, which visits each node exactly once. This results in a time complexity of O(n), where
- Space Complexity:
- C++: The recursive implementation uses the call stack for in-order traversal, which requires O(h) space, where
his the height of the tree. - Java: The Morris Traversal avoids recursion and uses constant space (O(1)) by modifying the tree structure temporarily.
- JavaScript: The recursive implementation uses the call stack, resulting in O(h) space complexity.
- Python: The forward and backward traversals are recursive, so the space complexity is O(h) due to the call stack.
- C++: The recursive implementation uses the call stack for in-order traversal, which requires O(h) space, where