Question

Given two binary search trees t1 and t2, you have to find minimum number of insertions to be done in t1 to make it structurally identical to t2

Answer 1

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    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) {
        int inserts=-1;
        if(A!=null && B==null)
           return inserts;
        if(A!=null && B!=null)
          {
              inserts=0;
              
          }
         if(A==null && B ==null)
         {
             inserts=0;
             return inserts;
         }
         if(A==null && B!=null)
         
        {
             
            int mid=min+(max-min)/2;
            A=new TreeNode(mid);
            inserts=1;
        }
        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+cntMatrixUtil(A.left,B.left,min,A.val)+cntMatrixUtil(A.right,B.right,A.val,max);
    }
}