Recover Binary Search Tree [Leetcode 99]

Leetcode problem, Tree Problem, Recursion

Amit Rai

Published in

Nerd For Tech

4 min readMay 30, 2022

This piece aims to solve the recover binary search tree Leetcode 99 problem

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: [10,5,15,6]
    10   
   /  \
  5    15   
 /
6 
  
Output: [10,6,15,5]
    10   
   /  \
  6   15   
 /
5

Example 2

Input: [3,1,4,null,null,2]   
  3  
 / \ 
1   4    
   /   
  2 
Output: [2,1,4,null,null,3]   
  2  
 / \ 
1   4    
   /   
  3

If you are preparing for your technical coding interview or you want to learn recursion to improve your problem-solving skills then you should check this udemy course Recursion Masterclass from Beginner to Advance level in C++ or you can checkout this recursion course on Skillshare.
If you want to learn ARKit 3 from beginner to expert level then click here to get the course and also you will get a 97% discount.
If you are passionate about learning mobile development for iOS and looking to take your iOS development skills to the next level, Core Data with CloudKit framework should be at the top of your list. Click here to get the course and also you will get a 97% discount.
Learn SwiftUI from Scratch click here to get the course because in this course we are going to build many apps using SwiftUI such as Facebook clone, News app, Notes app and much more.

Brute Force Approach

First, we will create one vector, we will traverse the tree in an In-Order fashion (you can use any traversal algorithm) and we will push back the element in a vector then we will sort the vector in ascending order.

After that again we will traverse the tree and we will change the value of the tree with our vector values but this time we have to traverse in an In-Order fashion because a binary search tree consists of elements lesser than the node to the left and the ones greater than the node to the right, an inorder traversal will give the elements in increasing order.

Code For Brute Force Approach

class Solution {
public:vector<int> v;void solve(TreeNode* root) {
        if(root == NULL) {
            return;
        }
        solve(root->left);
        v.push_back(root->val);
        solve(root->right);
    }int i = 0;
    void inOrderTraversal(TreeNode* root) {
        if(root == NULL) {
            return;
        }
        inOrderTraversal(root->left);
        root->val = v[i];
        i++;
        inOrderTraversal(root->right);
    }
    
    void recoverTree(TreeNode* root) {
        solve(root);
        sort(v.begin(), v.end());
        inOrderTraversal(root);
    }
};

Brute Force Approach Time & Space Complexity

Time Complexity: O(n)

Space Complexity: O(n)

Optimal Approach

In the brute force approach, the space complexity is O(n) we have to do better, If you think in the problem only two nodes are swapped, what we can do we can traverse the tree in an In-Order fashion and create one previous node and set the value to null after that we will traverse the tree and compare the current node value with the previous node value if the previous node is not null and previous node value is greater than the current node value than we can push back the previous and current node in our vector of pairs, because this is the node which is swapped.

We have all such pairs in our array. The array size will be 1 or 2 not more than 2 because only two nodes are swapped. if the array size is 1 that means only two adjacent nodes are swapped else the array size will be 2.

So we have to accordingly swap the numbers to get back to the original tree.

Code For Optimal Approach

class Solution {
public:TreeNode* prev = NULL;
vector<pair<TreeNode*, TreeNode*>> v;void solve(TreeNode* root) {
        if(root == NULL) {
            return;
        }
        
        solve(root->left);
        if(prev != NULL) {
            if(prev->val > root->val) {
                v.push_back(make_pair(root, prev));
            }
        }
        prev = root;
        solve(root->right);
    }
    
    void recoverTree(TreeNode* root) {
        solve(root);
        if(v.size() == 1) {
            swap(v[0].first->val, v[0].second->val);
        } else {
            swap(v[0].second->val, v[1].first->val);    
        }
        
    }
};

Optimal Approach Time & Space Complexity