Categories

# Merge Two Binary Trees

This is a LeetCode problem (617).

Let’s say we have the following two binary trees:

```        Tree 1                     Tree 2
1                         2
/ \                       / \
3   2                     1   3
/                           \   \
5                             4   7
```

Upon merging them, we should get this as the final result:

```Merged tree:
3
/ \
4   5
/ \   \
5   4   7
```

What this means is: If two nodes overlap, return the sum of those nodes.

Before looking at the solution, have a look at how a `TreeNode` is defined:

```function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
```

Note that `val` is the value of the current node, `left` is the reference to left node and `right` is the reference to the right node.

### Logic

The solution is to use a recursive function `mergeTrees( t1, t2 )` with the following logic inside it:

1. If `t1` doesn’t exist and `t2` exists, return `t2`. Similarly, if `t2` doesn’t exist and `t1` exists, return `t1`.
```if( !t1 || !t2 ) return t1 || t2;
```

2. If both exists then just return a new node by adding the values of those two nodes. Also, recursively merge left and right nodes (if any).

```return new TreeNode( t1.val + t2.val, mergeTrees( t1.left, t2.left ), mergeTrees( t1.right, t2.right ) );
```

### Final Solution

Once we put it all together, the full and final solution looks like this:

```var mergeTrees = function( t1, t2 ) {

if( !t1 || !t2 ) return t1 || t2;

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

};
```