Good morning! Here's our prompt for today.

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.

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

    'PASSED: `mergeTwoBinaryTrees(tree1, tree2)` should return a merged tree'

var assert = require('assert');

​

function Node(val) {

  this.val = val;

  this.left = this.right = null;

}

​

function mergeTwoBinaryTrees(tree1, tree2) {

  // Fill in this method

  return tree1;

}

​

function Node(val) {

  this.val = val;

  this.left = null;

  this.right = null;

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

​

var tree2 = new Node(5);

tree2.left = new Node(10);

tree2.left.left = new Node(17);

tree2.left.right = new Node(3);

tree2.right = new Node(8);

​

Tired of reading? Watch this video explanation!

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's our guided, illustrated walk-through.

How do I use this guide?