# Java Solution with explanation O(n+m)

• Explanation:
This is a straightforward tree traversal problem. Recursion is used to resolve the problem. The key here is to build the new tree based on 3 scenarios:
1.Both TreeNode t1 and t2 are null: base case, return null TreeNode
2.Both TreeNode t1 and t2 are not null: set the new TreeNode curr to the sum of t1 and t2, then recursively find curr.left and curr.right
3.Either TreeNode t1 or t2 is null: set the new TreeNode curr to either val of t1 or t2, then recursively find curr.left and curr.right
Big O:
The Big O is O(n+m), where n is the size of TreeNode t1 and m is the size of TreeNode t2, as both trees have to be traversed to generate the new tree. The big O then can be further generalized as O(n) or O(m), depending on if t1 or t2 is the larger tree

``````public class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
TreeNode curr = new TreeNode(0); //initialize tree node
if(t1==null && t2==null){
curr = null;
}
else if(t1!=null && t2!=null){
curr.val = t1.val + t2.val;
curr.left = mergeTrees(t1.left, t2.left);
curr.right = mergeTrees(t1.right, t2.right);
}
else{   //case where either t1==null or t2 == null
curr.val = (t1==null)?t2.val:t1.val;
curr.left = (t1==null)?mergeTrees(null, t2.left):mergeTrees(t1.left, null);
curr.right = (t1==null)?mergeTrees(null, t2.right):mergeTrees(t1.right, null);
}
return curr;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.