Teaching Kids Programming – Recursive Algorithm to Merge Two Binary Trees

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two binary trees node0 and node1, return a merge of the two trees where each value is equal to the sum of the values of the corresponding nodes of the input trees. If only one input tree has a node in a given position, the corresponding node in the new tree should match that input node.

Constraints
n ≤ 100,000 where n is the number of nodes in node0
m ≤ 100,000 where m is the number of nodes in node1

Merge Two Binary Trees by Recursion

When one of the Binary Tree is empty, we simply return another one. If both are non-empty, we can create a new Node with sum of two. Then, we can recursively merge the left and right sub trees.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeBinaryTrees(self, node0, node1):
        if node0 is None:
            return node1
        if node1 is None:
            return node0
        root = Tree(node0.val + node1.val)
        root.left = self.mergeBinaryTrees(node0.left, node1.left)
        root.right = self.mergeBinaryTrees(node0.right, node1.right)
        return root

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeBinaryTrees(self, node0, node1):
        if node0 is None:
            return node1
        if node1 is None:
            return node0
        root = Tree(node0.val + node1.val)
        root.left = self.mergeBinaryTrees(node0.left, node1.left)
        root.right = self.mergeBinaryTrees(node0.right, node1.right)
        return root

The Time Complexity is O(N+M) where N and M are the number of the nodes for two binary trees. And the space complexity is also O(Max(N, M)) as the new tree contains Max(N, M) nodes. The recursion space complexity is O(Max(H1, H2)) where the H1, and H2 are the heights for two binary trees.

See also: C++ Coding Exercise – How to Merge Two Binary Trees?

–EOF (The Ultimate Computing & Technology Blog) —