Merge Two Binary Trees

Medium
Tree Recursion Binary Tree
🏢Salesforce
0 views0 likes

Problem Description

Merge Two Binary Trees

Given two binary trees, merge them into a new binary tree. Each node in the new tree should hold a value 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.

Write a function that takes the roots of two binary trees and returns the root of the new merged tree.

Example 1: 

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

Example 2: 

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

Constraints:

  • The number of nodes in both trees is in the range [0, 1000].
  • Each node's value is an integer.

Hints

Use a recursive function to traverse both trees simultaneously.

Create a new tree node for each pair of corresponding nodes from the input trees.

Solution