CODEWITHSUNDEEP
algorithmbinary-treebinary-search-tree
CodeLover
CodeLover

Reputation: 118

Convert one BST to become structurally identical to other in minimum number of insertions

Given two binary trees T1 and T2, you have to find minimum number of insertions to be done in T1 to make it structurally identical to T2. Return -1 if not possible.

Notes

  1. Assume insertions are done in a normal fashion in the BSTs.
  2. Assume while inserting, if the value of a node v is equal to value being inserted, we insert it in left subtree of node v.
  3. You can insert any positive or negative integer.

Serialization : for each index i, 2*i is left child and 2*i+1 is right child, -1 if no child

Input 1: 

T1:  10 9 20

T2:  5 2 7 1 -1 -1 -1

 10                 5
 /\                / \
9  20             2   7
                 /
                1

If you insert 8 into T1, it will be structurally identical to T2. Hence answer is 1.

Input 2: 

T1:   10 9 20

T2:   5 -1 7

 10          5
 /\           \
9  20          7

You cannot make T1 and T2 structurally identical. Hence answer is -1.

My this code got accepted on platform, but i doubt it's correctness. I am not sure weather by allowing insertion of equal elements this code is correct or not.

Do we still need to check for value ranges to insert nodes in the tree ?

    int Solution::cntMatrix(TreeNode* A, TreeNode* B) {
      if(A==NULL && B==NULL) return 0;
      if(A==NULL) {
          int L=cntMatrix(A,B->left); if(L==-1) return -1;
          int R=cntMatrix(A,B->right);if(R==-1) return -1;
          return L+R+1;
      }
      if(B==NULL) return -1;
      int L=cntMatrix(A->left,B->left);   if(L==-1) return -1;
      int R=cntMatrix(A->right,B->right); if(R==-1) return -1;
      return L+R;
    }

Source : InterviewBit

Upvotes: 3

Views: 2356

Answers (6)

Babu Yadav
Babu Yadav

Reputation: 1

int cntMatrixUtil(TreeNode* A, TreeNode*B, int l1, int h1){
    if(A == NULL && B == NULL) return 0;
    if(A!= NULL && B == NULL) return -1;
    if(A == NULL && B != NULL){
        //you have to keep checking for all possible values at this position
        for(int i=l1; i<=h1; i++){
            int cntLeft = cntMatrixUtil(NULL, B->left, l1, i);
            int cntRight = cntMatrixUtil(NULL, B->right, i+1, h1);
            if(cntLeft == -1 || cntRight == -1) continue;
            return cntLeft+cntRight+1;
        }
        return -1;
    }else{
        int cntLeft = cntMatrixUtil(A->left, B->left, l1, A->val);
        int cntRight = cntMatrixUtil(A->right, B->right, A->val+1, h1);
        if(cntLeft == -1 || cntRight == -1) return -1;
        return  cntLeft + cntRight;
    }
} 

int Solution::cntMatrix(TreeNode* A, TreeNode* B) {
    return cntMatrixUtil(A,B, INT_MIN, INT_MAX);
}

Upvotes: 0

Prakhar Agrawal
Prakhar Agrawal

Reputation: 1022

Consider the following case:

5 10 8 -1 -1 -1

13 5 0 -1 -1 1 -1 3 2 -1 -1 3 -1 -1

This should ideally return -1, since tree 1 cannot be structurally converted to tree 2. However your computed value would be 4.

Upvotes: 0

data_3
data_3

Reputation: 1

you can try something like this, in python : (also DFS would be faster for this problem since you could return -1 faster)

    count = 0
    queue = [(T1,T2)]
    while queue:
        (t1, t2) = queue.pop()
        if not t1 and not t2: continue
        if t1 and not t2: return -1
        if t1 and not t2: count +=1
        queue.append((t1.left if t1 else None, t2.left))
        queue.append((t1.right if t1 else None, t2.right))
    return count

Upvotes: 0

joney_000
joney_000

Reputation: 21

Following solution is more accurate in terms of accuracy and performance: 


    public int cntMatrix(TreeNode A, TreeNode B) {
        return cntMatrixUtil(A,B,Integer.MIN_VALUE,Integer.MAX_VALUE);

    }

    public int cntMatrixUtil(TreeNode A, TreeNode B, int min,int max) {
        if(A!=null && B==null)
           return -1;
        int inserts=-1;
        if(A!=null && B!=null)inserts = 0;
        else inserts = 1;
        if(B==null && A==null)return 0;
        if(B !=null && A ==null)A = new TreeNode(min+(max-min)/2);
        int left = cntMatrixUtil(A.left, B.left, min, A.val);
        int right = cntMatrixUtil(A.right, B.right, A.val, max);
        if(left==-1 || right ==-1)return -1;
        return inserts + left + right;
    }

Upvotes: 0

Aitizazk
Aitizazk

Reputation: 342

You can solve this using Breadth first search. compare the no of nodes at each level if T1 has more nodes at a level than T2 simply return -1 else use a variable say count and at each level you can simply docount+=(No of nodes of T2 at level N) - (No of nodes of T1 at level N)

and then return count thats it.

Upvotes: 1

ElKamina
ElKamina

Reputation: 7807

If T1 has m elements and T2 has n elements, then the number of insertions required is n-m. Obviously. Because if you insert more, then T1 will have more elements and can never be structurally equivalent to T2.

The other questions are more interesting.

  1. Is it even possible? Simultaneously traversing both trees should answer this question.

  2. Most interesting question is, what to insert? For this you need to maintain a (min, max) limits and update it accordingly. Whenever you need to insert a number, pick from this range.

I am leaving out details for you to work out. But this is the gist.

Upvotes: 0

Related Questions