Categories
Uncategorized

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 ) );
    
};

Leave a Reply

Your email address will not be published. Required fields are marked *