Recover Binary Search Tree || Solution in C++ || Constant space

 Recover Binary Search Tree

We are given a tree such that exactly two values are swapped by mistake. We have to make it a Binary Search Tree by correcting that mistake.

Approach 1:

We know that the in-order traversal of the Binary Search Tree is always sorted. So we will store the inorder traversal of the given Binary Search Tree in a vector and find the two nodes which are causing the problem and swap them.
We will traverse the vector and find the element (the first node causing the problem, say t) whose value is greater than the value of the next node. We will also store the next node (say r). Now r need not be the element so we will traverse the remaining nodes. If any node having a value lesser than the value of r is found then update r to this node. finally, swap the values of t and r.

    Time Complexity:

        O(n): for traversing the tree,
        O(n): for traversing the vector
        overall O(n)

    Space Complexity:

        O(n): for storing elements in a vector

    C++ Code:

        class Solution {
    public:
    void recover(TreeNode* root) {
        vector<TreeNode*>v;
        inorder(root,v);
        int i;
        TreeNode* t;
        TreeNode* r;
        for( i=0;i<v.size()-1;i++){
            if(v[i]->val>v[i+1]->val){
                t=v[i];
                r=v[i+1];
                break;
            }
        }
        for(i;i<v.size()-1;i++){
            if(r->val>v[i+1]->val)r=v[i+1];
        }
        i=t->val;
        t->val=r->val;
        r->val=i;
    }
    void inorder(TreeNode* root,vector<TreeNode*>&v){
        if(root==NULL)return;
        inorder(root->left,v);
        v.push_back(root);
        inorder(root->right,v);
    }
};

Approach 2:

 In this approach, we will use the same concept as used in 1st but here will not use any extra space. we will get the problem causing nodes at the time of traversing the tree itself and we will swap their values.

    Time Complexity:

        O(n) : for traversing the Binary Search Tree

    Space Complexity:

        No extra space is used

    C++ Code:

    class Solution {
    public:
    TreeNode* first=NULL;
    TreeNode* last=NULL;
    TreeNode* prev=new TreeNode(INT_MIN);
    void recover(TreeNode* root) {
        inorder(root);
        swap(first->val,last->val);
    }
    void inorder(TreeNode* root){
        if(root==NULL)return;
        inorder(root->left);
        if(root->val<prev->val and prev){
            if(first==NULL){
                first=prev;
                last=root;
            }
            else{
                last=root;
            }
        }
        prev=root;
        inorder(root->right);
    }
};

Comments

Popular posts from this blog

NITs Gate Vlsi cutoff

Swap Nodes in Pairs using recursion in cpp