617. Merge Two Binary Trees LeetCode Solution

Last updated: February 19, 2025

In this guide, you will get 617. Merge Two Binary Trees LeetCode Solution with the best time and space complexity. The solution to Merge Two Binary Trees problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Merge Two Binary Trees solution in C++
Merge Two Binary Trees solution in Java
Merge Two Binary Trees solution in Python
Additional Resources

617. Merge Two Binary Trees LeetCode Solution image

Problem Statement of Merge Two Binary Trees

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].
-104 <= Node.val <= 104

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(\log n)

617. Merge Two Binary Trees LeetCode Solution in C++

class Solution {
 public:
  TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (root1 == nullptr && root2 == nullptr)
      return nullptr;
    const int val = (root1 == nullptr ? 0 : root1->val) +
                    (root2 == nullptr ? 0 : root2->val);
    TreeNode* root = new TreeNode(val);
    root->left = mergeTrees(root1 == nullptr ? nullptr : root1->left,
                            root2 == nullptr ? nullptr : root2->left);
    root->right = mergeTrees(root1 == nullptr ? nullptr : root1->right,
                             root2 == nullptr ? nullptr : root2->right);
    return root;
  }
};
/* code provided by PROGIEZ */

617. Merge Two Binary Trees LeetCode Solution in Java

class Solution {
  public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null)
      return null;
    final int val = (root1 == null ? 0 : root1.val) + (root2 == null ? 0 : root2.val);
    TreeNode root = new TreeNode(val);
    root.left = mergeTrees(root1 == null ? null : root1.left, root2 == null ? null : root2.left);
    root.right = mergeTrees(root1 == null ? null : root1.right, root2 == null ? null : root2.right);
    return root;
  }
}
// code provided by PROGIEZ

617. Merge Two Binary Trees LeetCode Solution in Python

class Solution:
  def mergeTrees(
      self,
      root1: TreeNode | None,
      root2: TreeNode | None,
  ) -> TreeNode | None:
    if not root1 and not root2:
      return None
    val = (root1.val if root1 else 0) + (root2.val if root2 else 0)
    root = TreeNode(val)
    root.left = self.mergeTrees(root1.left if root1 else None,
                                root2.left if root2 else None)
    root.right = self.mergeTrees(root1.right if root1 else None,
                                 root2.right if root2 else None)
    return root
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents