Merge Two Binary Trees (Medium)

Good evening! Here's our prompt for today.

You may see this problem at Yelp, Uber, Hashicorp, Gitlab, Checkout Com, Auth0, Samsara, Figma, Thoughtspot, Netskope, Automattic, Cohesity, Keeptruckin, Veeam, Tradeshift, and At T.

Merging Two Binary Trees

The Problem Statement

You are presented with two binary trees. Your task is to merge these trees into a single, new binary tree.

The Overlap Rule

Here's the catch: some nodes in these two trees may overlap when you try to put them together. When that happens, the new node's value in the merged tree will be the sum of the overlapping nodes. For instance, consider the right leaf node in Tree 1 with a value of 2 and the right node in Tree 2 with a value of 3. In the merged tree, the corresponding node would have a value of 5 (2 + 3).

The No-Overlap Rule

If nodes don't overlap, the node value from the existing tree is simply carried over into the new tree.

An Example to Illuminate

Here's a quick example to make this more concrete:

1  Tree 1                 Tree 2         
2    1                       2               
3   / \                     / \              
4  3   2                   1   3             
5 /                         \   \            
65                           4   7           
7
8Resulting Merged Tree:
9    3
10   / \
11  4   5
12 / \   \ 
135   4   7

Boilerplate Code

You can assume that the nodes in the tree are defined as follows in JavaScript:

1function Node(val) {
2  this.val = val;
3  this.left = this.right = null;
4}

Constraints and Expectations

• Both trees will contain no more than 100,000 nodes.
• Node values will always be integers and fall in the range -1,000,000,000 to 1,000,000,000.
• Aim for a time complexity of (O(m+n)), where (m) and (n) are the number of nodes in each of the binary trees, respectively.

Your task is to start merging from the root nodes of both trees and produce a new tree that satisfies the above conditions.