Good afternoon! 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
to1,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
# class Node:
# def __init__(val):
# this.val = val
# this.left = None
# self.right = None
def merge_two_binary_trees(tree1, tree2):
# fill in
return tree1
# Node definition
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# Regular binary trees
tree1 = Node(4)
tree1.left = Node(1)
tree1.right = Node(3)
tree2 = Node(5)
tree2.left = Node(10)
tree2.left.left = Node(17)
tree2.left.right = Node(3)
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 how we would solve this problem...
How do I use this guide?
Unveiling the Approach: Merging Binary Trees
Step 1: The Simple Case - Merging Root Nodes
Before diving into the complexities of merging full-fledged binary trees with all their branches and leaves, let's start simple. We'll consider the most basic case: two trees each containing only a root node.
Here's the example we'll work through:
1 1st Tree 2nd Tree Merged Tree
2 3 1 4
The Strategy for Merging Root Nodes
- Check for Empty Trees: First, ensure that neither of the root nodes is
null
. - Sum the Values: If both roots exist, sum their values to create a new root node for the merged tree.
- Create the Merged Root: Instantiate a new node with the sum as its value.
Code Snippet for Merging Root Nodes
Here's how you would implement these steps.
Great! We've successfully merged two single-node trees. But what happens when these trees have children?
xxxxxxxxxx
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def merge_trees(root1, root2):
# Check for empty trees
if not root1:
return root2
if not root2:
return root1
# Sum the root nodes' values
sum_val = root1.val + root2.val
# Create the merged root
merged_root = Node(sum_val)
return merged_root
# Create individual root nodes for 1st and 2nd trees
root1 = Node(3)
root2 = Node(1)
# Merge and get the new root
merged_root = merge_trees(root1, root2)
print(f"Merged Root Value: {merged_root.val}") # Output should be 4
The Human Approach to Merging Trees
Imagine you have two different trees. To combine them into one tree, you'd naturally start by looking at the top piece of each puzzle—the root. You'd combine these roots to create a new root for the merged tree.
Then, you'd proceed down each branch, combining corresponding pieces (nodes) from each tree. If a branch exists in one tree but not the other, you'd simply include the existing branch in the new tree. If a branch exists in both trees, you'd combine them to form a new branch.
Running Through Examples to Identify Patterns
Example 1
- Tree 1: A single node with value 3
- Tree 2: A single node with value 1
- Merged Tree: A single node with value (3 + 1 = 4)
Example 2
- Tree 1:
- Root: 3
- Left child: 5
- Tree 2:
- Root: 1
- Right child: 4
- Merged Tree:
- Root: (3 + 1 = 4)
- Left child: 5 (from Tree 1)
- Right child: 4 (from Tree 2)
Example 3
- Tree 1:
- Root: 2
- Left child: 3
- Right child: 4
- Tree 2:
- Root: 1
- Left child: 4
- Right child: 5
- Merged Tree:
- Root: (2 + 1 = 3)
- Left child: (3 + 4 = 7)
- Right child: (4 + 5 = 9)
Observations
- Roots Merge: The root of the merged tree is the sum of the roots of the individual trees.
- Branching Logic: If a node exists in one tree but not in the other, the node from the existing tree is included in the merged tree.
- Recursive Nature: The process for merging the children of two nodes looks suspiciously similar to the process for merging the roots. This suggests a recursive solution.
Armed with these observations, we can confidently proceed to code our brute-force solution.
Build your intuition. Fill in the missing part by typing it in.
Complete the sentence. The merge rule is: if two nodes overlap, the resultant node is the _ of the two nodes.
Write the missing line below.
Let's test your knowledge. Is this statement true or false?
True or False? The merging step does not have to start from the root nodes of both trees.
Press true if you believe the statement is correct, or false otherwise.
Visualizing the Merging Process
The picture truly is worth a thousand words. In this diagram, we see Tree 1 with a root node of 3 and Tree 2 with a root node of 1. As per our observation #1—"Roots Merge"—we combine these roots to create a new root for the merged tree, which has a value of (3 + 1 = 4).
The Steps in the Process
Start at the Roots: We begin with the root nodes of both Tree 1 and Tree 2. These are 3 and 1, respectively.
Merge the Roots: We add the values of these root nodes together. (3 + 1 = 4)
Create the Merged Root: We then use this sum to create the root node of our new, merged tree.
xxxxxxxxxx
/*
1st Tree 2nd Tree Merged Tree
3 1 4
/ \ / \ / \
1 3 4
*/
Moving Down to the Left Child Node
Excellent! We've successfully merged the root nodes. Now, it's time to move on to the children nodes, starting with the left child. Just as we merged the root nodes, we'll use the same strategy for the children nodes.
A Step-by-Step Look
Locate the Left Children: Per the current example, let's assume that Tree 1 has a left child with a value of 1, and Tree 2 has a left child with a value of 3.
Merge the Left Children: As with the roots, we sum the values of these left children nodes. (1 + 3 = 4)
Create the Merged Left Child: This sum becomes the value of the new left child node in our merged tree.
Result of the Operation
By following these steps, we end up with a merged tree that has a root node of 4 and a left child node of 4.
The Recursive Nature
What's nice about this process is its inherently recursive nature. Once we've figured out how to merge the root and one set of children nodes, we can apply the same logic to all subsequent layers of the tree. This sets us up perfectly for the coding phase, where recursion will help us elegantly navigate and merge the trees.
Build your intuition. Click the correct answer from the options.
How many parameters does the merge tree function need to perform a merger?
Click the option that best answers the question.
- 0
- 1
- 2
- 3
Build your intuition. Click the correct answer from the options.
Which of the following is the correct order of visiting nodes for a pre-order traversal?
Click the option that best answers the question.
- left, right, root
- right, left, root
- root, left, right
- root, right, left
Identifying the Traversal Pattern
The pattern you're seeing is indicative of a tree traversal algorithm. Specifically, what we're doing can be modeled as a Preorder Traversal.
Why Preorder Traversal?
In preorder traversal, we visit the root first, then traverse the left subtree, and finally the right subtree. This is exactly what we're doing while merging the trees:
- Visit the Root: Merge the root nodes of both trees.
- Traverse the Left Subtree: Merge the left subtrees of both trees.
- Traverse the Right Subtree: Merge the right subtrees of both trees.
Here’s how the Preorder Traversal skeleton code might look in JavaScript:
1function preOrder(node) {
2 if (!node) return;
3 // Perform some operation on the current node (like merging)
4 preOrder(node.left); // Traverse the left subtree
5 preOrder(node.right); // Traverse the right subtree
6}
Adaptation for Merging
To adapt this for merging, we would:
- Sum the current nodes from both trees and create a new node in the merged tree.
- Recursively perform this operation for left and right children.
The skeleton code for Preorder Traversal gives us a good framework to build upon for our merging function.
Traversal is the key
Since we started we'll need to eventually return a merged root, let's go with an pre-order traversal. Pseudocode as follows:
xxxxxxxxxx
function preOrder(tree1, tree2) {
if (tree1 == null) {
return tree2;
}
if (tree2 == null) {
return tree1;
}
return tree1.val + tree2.val;
// Do the above on both of their left children
preOrder(tree1.left, tree2.left)
// Do the above on both of their right children
preOrder(tree1.right, tree2.right)
}
Applying this to the problem at hand, doSomeOperation()
for us would mean checking the currently investigated node position at both the first and second trees, and deciding what to return.
But what do we need to get back? Here's an operation that might work given our examples:
xxxxxxxxxx
if (tree1 == null) {
return tree2;
}
if (tree2 == null) {
return tree1;
}
tree1.val = tree1.val + tree2.val
return tree1;
The above code isn't exactly right though-- we're not returning a sum of the two values after checking for null
on both, but rather we should be returning a merged node object. To save space, if there are values at both nodes, let's just add them onto the first tree and simply return it.
Try this exercise. Could you figure out the right sequence for this list?
Arrange the following instructions into the correct order to merge two binary trees recursively:
Press the below buttons in the order in which they should occur. Click on them again to un-select.
Options:
- If there exists a node:
- Use pre-order traversal on the first tree
- Return the root of the updated first tree
- Continue this process for left subtrees
- Check to see if both the tree nodes are null (there exists no node in either tree)
- If there exists one node, update the first tree with the value of that node
- Continue this process for right subtrees
- If there exists two nodes, update the first tree with the sum of the values of both nodes
This needs to be done at every recurrence as we traverse through the trees. However, the traversal needs to be done before we return tree1-- the intuition being that we need to adjust the children of each node before we can give it back. In other words, we should write the merge results on the first tree before presenting it back in our method.
xxxxxxxxxx
function mergeTwoBinaryTrees(tree1, tree2) {
if (tree1 == null) {
return tree2;
}
if (tree2 == null) {
return tree1;
}
tree1.val += tree2.val
tree1.left = mergeTwoBinaryTrees(tree1.left, tree2.left);
tree1.right = mergeTwoBinaryTrees(tree1.right, tree2.right);
return tree1;
}
Understanding Time Complexity:
You've got it spot on! The time complexity of perfectly captures the nature of this problem.
Why ?
- Every Node Visited Once: In the process of merging, each node in both trees is visited exactly once.
- Single Operation Per Node: At each visit, we perform a constant amount of work (i.e., summing node values and creating a new node).
Considering that there are nodes in the first tree and nodes in the second tree, it's quite straightforward to conclude that the overall time complexity is .
The Intuition
Think of it like two separate lists that you need to merge into one. You have to look at each element at least once in both lists to accomplish this. In our case, the lists are just a bit more complex, structured as binary trees. But the fundamental idea remains the same: you have to touch every node at least once.
Try this exercise. Click the correct answer from the options.
What is the time complexity of the recursive tree merger algorithm?
Click the option that best answers the question.
- O(1)
- O(n!)
- O(n log n)
- O(n)
One Pager Cheat Sheet
- The sum of overlapping nodes is used to create the merged tree, while nodes that do not overlap remain unchanged, within the constraints of
O(m+n)
time complexity and-1000000000
to1000000000
for node values. - We can
merge trees
with just root nodes togauge
how we'dperform
this exercise fortrees with children
. - We can
brute force
solve a problem byvisualizing
how a human would do it, and running through examples to find patterns. - The merge rule states that when two nodes overlap, their attributes and properties are combined
summarily
to form a resultant node. - The merge rule allows any two
overlapping
nodes to be combined, so it does not have to start from the root nodes of both trees. - We could
sum up
thenode values
of two trees, byprocessing at the root
of each one, and thenchecking for left and right children
, according torule #2
. - We
scan
the tree from left to right andsum up
the values we find between eachnode
, returning4
from the root's left child. - The merge tree function
combines
the twotree nodes
byadding
the two elements within them together toget the result
. - The algorithm of
pre-order traversal
is a Depth-First Search which visits the nodes of a tree in the root, left, right order. - We can
traverse
both trees simultaneously andcheck
their values at each step to create a pattern. - The
pre-order traversal
technique is the key to returning a merged root. - Checking the
node position
of thecurrently investigated
element at thefirst
andsecond
trees usingdoSomeOperation()
can determine what toreturn
. - We should
merge
the two nodes by adding their values onto the first tree, and then simply return it. - The process of merging two binary trees recursively begins with a pre-order traversal of the first tree, checking the nodes of both trees, and then updating the first tree with the sum of their values before continuing with the subtrees.
- We should
traverse
both trees beforereturning
tree1, writing the merge results in the process. - We traverse through
both
binary trees at once with atime complexity
of O(m+n), allowing us to process one node ofeach tree
per iteration. - The
time complexity
of the recursive tree merger algorithm is O(n), as it only traverses the larger tree, resulting in a worst-case of O(n) nodes.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
print("Nice job, 2/2 tests passed!")
# class Node:
# def __init__(val):
# this.val = val
# this.left = None
# self.right = None
def merge_two_binary_trees(tree1, tree2):
if tree1 is None:
return tree2
if tree2 is None:
return tree1
tree1.val += tree2.val
tree1.left = merge_two_binary_trees(tree1.left, tree2.left)
tree1.right = merge_two_binary_trees(tree1.right, tree2.right)
return tree1
# Node definition
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# Regular binary trees
tree1 = Node(4)
tree1.left = Node(1)
tree1.right = Node(3)
Great job getting through this. Let's move on.
If you had any problems with this tutorial, check out the main forum thread here.