Build Identical Trees

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
- Assume insertions are done in a normal fashion in the BSTs.
- 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.
- You can insert any positive or negative integer.

Example :

Input 1: 

T1:       10
         / \
        9   20

T2:       5
         / \
        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
           \
            7

You cannot make T1 and T2 structurally identical. Hence answer is -1.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Build Identical Trees on Interview Code Editor
1169 successful submissions.
Click here to start solving coding interview questions