LeetCodee

617. Merge Two Binary Trees

Problem Description

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:

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, 2000]
  • -10^4 <= Node.val <= 10^4

Solution

Python Solution

# 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, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
            
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        
        return root1

Time Complexity: O(min(n1, n2))

Where n1 and n2 are the number of nodes in the trees.

Space Complexity: O(min(h1, h2))

Where h1 and h2 are the heights of the trees (due to recursion stack).

Java Solution

/**
 * 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 root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        
        return root1;
    }
}

Time Complexity: O(min(n1, n2))

Where n1 and n2 are the number of nodes in the trees.

Space Complexity: O(min(h1, h2))

Where h1 and h2 are the heights of the trees (due to recursion stack).

C++ Solution

/**
 * 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* root1, TreeNode* root2) {
        if (!root1) {
            return root2;
        }
        if (!root2) {
            return root1;
        }
        
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        
        return root1;
    }
};

Time Complexity: O(min(n1, n2))

Where n1 and n2 are the number of nodes in the trees.

Space Complexity: O(min(h1, h2))

Where h1 and h2 are the heights of the trees (due to recursion stack).

JavaScript Solution

/**
 * 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} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function(root1, root2) {
    if (!root1) {
        return root2;
    }
    if (!root2) {
        return root1;
    }
    
    root1.val += root2.val;
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right, root2.right);
    
    return root1;
};

Time Complexity: O(min(n1, n2))

Where n1 and n2 are the number of nodes in the trees.

Space Complexity: O(min(h1, h2))

Where h1 and h2 are the heights of the trees (due to recursion stack).

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode MergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        
        root1.val += root2.val;
        root1.left = MergeTrees(root1.left, root2.left);
        root1.right = MergeTrees(root1.right, root2.right);
        
        return root1;
    }
}

Time Complexity: O(min(n1, n2))

Where n1 and n2 are the number of nodes in the trees.

Space Complexity: O(min(h1, h2))

Where h1 and h2 are the heights of the trees (due to recursion stack).

Approach Explanation

The solution uses a recursive approach to merge two binary trees:

  1. Key Insights:
    • Recursive tree traversal
    • Node value summation
    • Null node handling
    • Tree modification
  2. Algorithm Steps:
    • Handle base cases (null nodes)
    • Sum node values
    • Recursively merge left subtrees
    • Recursively merge right subtrees

Implementation Details:

  • Recursive function
  • Node value addition
  • Tree modification
  • Null checks

Optimization Insights:

  • In-place modification
  • Early termination
  • Reuse existing nodes
  • Minimal space usage

Edge Cases:

  • Empty trees
  • Single node trees
  • Unbalanced trees
  • Different tree heights