Code Implementation

# 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: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1 and not t2:
            return None
        if not t1:
            return t2
        if not t2:
            return t1
        merged = TreeNode(t1.val + t2.val)
        merged.left = self.mergeTrees(t1.left, t2.left)
        merged.right = self.mergeTrees(t1.right, t2.right)
        return merged
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1 && !t2) return nullptr;
        if (!t1) return t2;
        if (!t2) return t1;
        TreeNode* merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);
        return merged;
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode() {}
//     TreeNode(int val) { this.val = val; }
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return null;
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function(t1, t2) {
    if (!t1 && !t2) return null;
    if (!t1) return t2;
    if (!t2) return t1;
    let merged = new TreeNode(t1.val + t2.val);
    merged.left = mergeTrees(t1.left, t2.left);
    merged.right = mergeTrees(t1.right, t2.right);
    return merged;
};
      

Problem Description

You are given two binary trees, t1 and t2. You need to merge them into a new binary tree. The merging rule is simple: if two nodes overlap (i.e., both trees have a node at the same position), their values are summed and become the value of the new node in the merged tree. If only one tree has a node at a given position, that node is used directly in the merged tree.

The function should return the root of the new merged tree. The input trees are not modified, and you should not reuse the nodes from the original trees in the merged tree.

• Each tree node contains an integer value.
• If both input trees are empty, the result is an empty tree (i.e., null).
• Only one valid merged tree should be returned.

Thought Process

At first glance, merging two binary trees might seem complicated, especially if you try to handle all possible tree shapes and missing nodes at once. A brute-force approach could involve traversing both trees separately and then combining their results, but this quickly becomes messy.

However, if you think recursively, the problem becomes much more manageable. For each position in the trees, you can:

• Sum the values if both nodes exist.
• Use the existing node if only one tree has a node at this position.
• Move to the left and right children, repeating the process.

This recursive strategy naturally handles trees of different shapes and sizes, and it avoids unnecessary complexity.

Solution Approach

We use a recursive algorithm to merge the two trees. Here’s a step-by-step breakdown:

1. Base Cases:
   • If both input nodes are null, return null (no node to merge).
   • If only one node is null, return the non-null node (no merging needed).
2. Recursive Step:
   • If both nodes exist, create a new node whose value is the sum of the two nodes' values.
   • Recursively merge the left children of both nodes to form the left child of the new node.
   • Recursively merge the right children of both nodes to form the right child of the new node.
3. Return:
   • Return the newly created node as the merged result for this subtree.

This approach is elegant because it mirrors the structure of the trees and handles all cases in a clean, readable way.

Example Walkthrough

Consider the following input trees:

      Tree 1:       1
                   / \
                  3   2
                 /
                5

      Tree 2:       2
                   / \
                  1   3
                   \   \
                    4   7
  

Let's merge them step-by-step:

1. Root: 1 (from Tree 1) + 2 (from Tree 2) = 3
2. Left Child: 3 (Tree 1) + 1 (Tree 2) = 4
   • Left of left: 5 (Tree 1) + null (Tree 2) = 5
   • Right of left: null (Tree 1) + 4 (Tree 2) = 4
3. Right Child: 2 (Tree 1) + 3 (Tree 2) = 5
   • Left of right: null (Tree 1) + null (Tree 2) = null
   • Right of right: null (Tree 1) + 7 (Tree 2) = 7

The merged tree:

          3
         / \
        4   5
       / \   \
      5   4   7
  

Each step only considers the current pair of nodes, and the recursion takes care of the rest.

Time and Space Complexity

• Brute-force Approach:
  • If you tried to traverse both trees separately and then merge their traversals, you might end up with O(N + M) time and space, where N and M are the number of nodes in the two trees.
• Optimized Recursive Approach:
  • Time Complexity: O(N), where N is the total number of nodes in both trees. Each node is visited once.
  • Space Complexity: O(H), where H is the height of the merged tree. This is the maximum depth of the recursion stack.

The recursive approach is optimal because it only processes each node once and uses space proportional to the tree's height.

Summary

To merge two binary trees, a recursive solution elegantly handles all cases by summing overlapping nodes and reusing existing nodes when only one exists. This approach is both simple and efficient, with clear base cases and recursive steps that mirror the structure of the trees. The algorithm is optimal in both time and space, making it an excellent example of using recursion to solve tree problems.