Problem Statement: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

My solution for the problem:

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
         // in case if either is null, directly return one of the nodes depending on the availablity.
         if(t1==null)  return t2;
         if(t2==null)  return t1;
         TreeNode left=mergeTrees(t1.left,t2.left);
         TreeNode right=mergeTrees(t1.right,t2.right);
         return t1;

I have calculated the worst-case time-complexity of the above code as O(Min.(Size of t1,Size of t2)) but I am not sure about it? Please share your analysis of it.


closed as off-topic by Antot, Mast, Sᴀᴍ Onᴇᴌᴀ, t3chb0t, Ludisposed Jan 8 '18 at 8:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ @Antot If you think it is a duplicate question, mark it as a duplicate. \$\endgroup\$ – pacmaninbw Jan 6 '18 at 15:14
  • \$\begingroup\$ @pacmaninbw: it's not duplicate, it's about code that copy-pasted from elsewhere. \$\endgroup\$ – Antot Jan 6 '18 at 15:24
  • \$\begingroup\$ I suggest you ask a question on codereview.meta.stackexchange.com/questions about this. Unless it is copying your code I don't think there is a rule here about copy and paste. \$\endgroup\$ – pacmaninbw Jan 6 '18 at 15:32
  • \$\begingroup\$ @pacmaninbw I think the help center states it has to be code you own. \$\endgroup\$ – Mast Jan 6 '18 at 15:52
  • \$\begingroup\$ @Antot it is my solution, the solution you have shared is different. it creates a new tree entirely where as this solution uses one of the trees in provided in the input. \$\endgroup\$ – Abhiroj Panwar Jan 6 '18 at 16:42

The time complexity of the algorithm is linear, proportional to the number of nodes in the trees. The worst case is when both trees have the same shape, then all the nodes in both trees will be visited. More generally, the number of nodes visited is proportional to min(size(t1), size(2)).

I don't understand why the question is tagged with , this posted solution should pass just fine.

A few minor improvements are possible.

  • The left and right local variables are redundant, you could assign directly to the fields of t1
  • The statement t2=null is completely unnecessary
  • Spaces around operators (like =) would make the code easier to read

Like this:

if (t1 == null) return t2;
if (t2 == null) return t1;

t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;

Not the answer you're looking for? Browse other questions tagged or ask your own question.