Leet Code :: Merge Binary Tree :: Time Complexity [closed]

Question

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);
         t1.val=t1.val+t2.val;
         t1.left=left;
         t1.right=right;
         t2=null;
         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.

Answer 1

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 time-limit-exceeded, 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;