Table of Contents
Problem Statement
The Recover Binary Search Tree LeetCode Solution – “Recover Binary Search Tree” states that given the root of the binary search tree, where the values of exactly two nodes are swapped by mistake. We need to recover the tree without changing its structure.
Example:
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation:
- Nodes with values 1 and 3 are swapped by mistake.
- Swap these two values and we have our new recovered binary search tree.
Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation:
- Nodes with values 2 and 3 are swapped by mistake.
- Swap these two values and we have our new recovered binary search tree.
Approach
Idea:
- The main idea to solve this problem is to use Inorder Traversal of the Binary Search Tree.
- In an Inorder traversal of a Binary Search Tree, It generated the sequence of node’s values in increasing order.
- Now, Consider when all the node values are at their correct place in a Binary Search Tree. Let’s find the prefix maximum of such sorted sequence. Then, we can easily observe that for every integer in the sequence prefix maximum [i] = node value at the current position.
- When two node values are swapped, then there exists a subarray where the above criteria don’t hold. Hence, we need to find the starting and ending positions of such subarray.
- Swap the node values at this two-position and our binary search tree is recovered.
- Perform the inorder traversal of the tree in a recursive fashion and find the starting and ending node of the required subarray.
- Swap the two-node values found in the above step.
Code
Recover Binary Search Tree Leetcode C++ Solution:
class Solution {
public:
int maxi = INT_MIN;
TreeNode* node1 = nullptr;
TreeNode* node2 = nullptr;
void inorder(TreeNode* root){
if(root==nullptr){
return;
}
inorder(root->left);
maxi = max(maxi,root->val);
if(maxi==root->val){
if(node2==nullptr){
node1 = root;
}
}
else{
node2 = root;
}
inorder(root->right);
}
void recoverTree(TreeNode* root) {
inorder(root);
swap(node1->val,node2->val);
}
};Recover Binary Search Tree Leetcode Java Solution:
class Solution {
private TreeNode first;
private TreeNode second;
private TreeNode pre;
public void recoverTree(TreeNode root) {
if(root==null) return;
first = null;
second = null;
pre = null;
inorder(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
private void inorder(TreeNode root){
if(root==null) return;
inorder(root.left);
if(first==null && (pre==null ||pre.val>=root.val)){
first = pre;
}
if(first!=null && pre.val>=root.val){
second = root;
}
pre = root;
inorder(root.right);
}
}Complexity Analysis for Recover Binary Search Tree Leetcode Solution
Time Complexity
The time complexity of the above code is O(N) since we traverse the entire binary search tree once where N = a total number of nodes in the tree.
Space Complexity
The space complexity of the above code is O(1) [here we’re not considering the space due to recursion stack] since we’re using constant space.