# Simple Java recursive solution - O(n)

• ``````public class Solution {
public TreeNode merge(TreeNode t1, TreeNode t2) {
if(t1 == null && t2 == null) {
return null;
}

TreeNode newNode = new TreeNode(-1);
if(t1 == null) {
newNode.val = t2.val;
newNode.left = merge(null, t2.left);
newNode.right = merge(null, t2.right);
}
else if(t2 == null) {
newNode.val = t1.val;
newNode.left = merge(t1.left, null);
newNode.right = merge(t1.right, null);
}
else {
newNode.val = t1.val + t2.val;
newNode.left = merge(t1.left, t2.left);
newNode.right = merge(t1.right, t2.right);
}

return newNode;
}
}
``````

• Why is this line needed?

TreeNode newNode = new TreeNode(-1);

I was reusing t1 here but otherwise had the same code and the new nodes were not getting created. But the sums were working correctly

• @FrankUnderwood
The question exclusively demanded "You need to merge them into a new binary tree." That is why I created the new node

• @soumyadeep2007 what do you mean by TreeNode(-1), I didn't find the constructor of the TreeNode

• @KyleGaoShijie This is the definition for a TreeNode which is a LeetCode supplied type:

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
``````

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