# Tree - Merge Two Binary Trees

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

PreOrder dfs()

## Problem

You are given two binary trees `root1`

and `root2`

. Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree. Return *the merged tree*.

**Note:** The merging process must start from the root nodes of both trees.

**Example 1:**

1
2

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

**Example 2:**

1
2

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

## Solution

A PreOrder DFS can be used to solve this. We nee to traverse the trees together and sum the node value.

Start with the base condition. In case both of the nodes are `None`

return `None`

.

1
2

if not root1 and not root2:
return None

Next, just like LinkedLink merge, we need to make sure if one of the root is `None`

we set the `val`

to `0`

.

1
2

val1 = root1.val if root1 else 0
val2 = root2.val if root2 else 0

Create a new node with the summed value.

1

root = TreeNode(val1+val2)

Create new `left`

node by traversing through `left`

node of both `root1`

and `root2`

. (same for `right`

node). `merge_trees`

is called recursively here.

1
2
3
4

root.left = merge_trees(root1.left if root1 else None,root2.left if root2 else None)
root.right = merge_trees(root1.right if root1 else None,root2.right if root2 else None)
return root

Here is another version (if this helps).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def merge_tree(root1, root2):
def dfs(root1, root2):
if not root1 and not root2:
return None
if not root1 or not root2:
if root1 is not None:
root = TreeNode(val=root1.val)
root.left= dfs(root1.left, None)
root.right= dfs(root1.right, None)
return root
elif root2 is not None:
root = TreeNode(val=root2.val)
root.left= dfs(None, root2.left)
root.right= dfs(None,root2.right)
return root
val1=root1.val if root1 is not None else 0
val2=root2.val if root2 is not None else 0
root = TreeNode(val=val1+val2)
root.left= dfs(root1.left, root2.left)
root.right= dfs(root1.right, root2.right)
return root
return dfs(root1,root2)

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def merge_trees(root1, root2):
if not root1 and not root2:
return None
val1 = root1.val if root1 else 0
val2 = root2.val if root2 else 0
root = TreeNode(val1+val2)
root.left = merge_trees(root1.left if root1 else None,
root2.left if root2 else None)
root.right = merge_trees(
root1.right if root1 else None, root2.right if root2 else None)
return root