Skip to main content

Merge Two Binary Trees

Question​

Given two binary trees, write a function to merge them so that the resulting tree contains all of the elements of both trees.

Example 1
Input: 
Tree 1:
     1
   /   \
  3     2
 / \   / \
5   4 7   8

Tree 2:
     9
   /   \
  10    11
 / \   / \
12  13 14  15

Output:
     10
   /   \
  12    13
 / \   / \
17  14 21  23

Solution​

all//Merge Two Binary Trees.py


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def mergeTrees(self, t1, t2):
        if not t1:
            return t2
        if not t2:
            return t1

        t1.val += t2.val
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)

        return t1