Merge Two Binary Trees Leetcode Problem 617 [Python Solution]

If you’re a beginner in the world of coding, or even if you’re more experienced, tackling LeetCode problems can be a great way to sharpen your skills and learn new techniques.

In this blog post, we’ll dive into the Merge Two Binary Trees problem, specifically LeetCode Problem 617. We’ll provide you with a Python solution and break down the problem step by step to make it easy to understand.

Problem Overview

You are given two binary trees, root1 and root2.

The task is to merge these two trees into a new binary tree.

The merge rule is simple: if two nodes overlap (exist in both trees), add their values together as the new value for the merged node.

If a node is only present in one of the trees, use that node as is for the merged tree.

Here’s an example to illustrate this:

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].
The values of nodes are in the range [-104, 104].

To solve this problem, we’ll use a recursive approach.

We’ll traverse both trees simultaneously, merging nodes as needed.

Understanding Constraints

Before we dive into the solution, let’s understand the constraints:

The number of nodes in both trees is in the range [0, 2000]: This means we need an efficient solution since the input can be large.

The time complexity of our solution is O(n + m), where n is the number of nodes in root1, and m is the number of nodes in root2.

Node values can be in the range [-104, 104]: This constraint tells us that we should handle both positive and negative values for the node’s data.

Now, let’s get into the solution.

Merge Two Binary Trees LeetCode Problem Solution

We’ll define a Python function to merge the two binary trees.

We’ll call this function mergeTrees.

Here’s the code:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
    if not t1 and not t2:
        return None

    v1 = t1.val if t1 else 0
    v2 = t2.val if t2 else 0
    root = TreeNode(v1 + v2)

    root.left = self.mergeTrees(t1.left if t1 else None, t2.left if t2 else None)
    root.right = self.mergeTrees(t1.right if t1 else None, t2.right if t2 else None)
    return root

This code defines a TreeNode class to represent the nodes of the binary tree.

The mergeTrees function takes two parameters, t1 and t2, which are the root nodes of the two binary trees we want to merge.

1. Bruteforce Approach

The algorithm uses a recursive approach to merge the trees.

Let’s break it down step by step:

If both t1 and t2 are None (null nodes), we return None because there’s nothing to merge.
We get the values v1 and v2 from the nodes t1 and t2 or set them to 0 if the nodes are None.
We create a new TreeNode called root with the value v1 + v2.
We recursively merge the left and right subtrees of t1 and t2 by calling mergeTrees on the left and right children.

We pass None if the corresponding child node is None.

Finally, we return the root, which is the merged binary tree.

This approach efficiently merges the two trees, creating a new tree with the merged values.

The time complexity of this solution is O(n + m), where n and m are the numbers of nodes in t1 and t2, respectively.

Python Code Solution

Now, let’s provide you with the Python code solution for the Merge Two Binary Trees problem:

View on GitHub ➹

def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:    
        def merger(root1, root2):
            if not root1 and not root2:
                return None

            v1 = root1.val if root1 else 0
            v2 = root2.val if root2 else 0
            root = TreeNode(v1 + v2)

            root.left = merger(root1.left if root1 else None, root2.left if root2 else None)
            root.right = merger(root1.right if root1 else None, root2.right if root2 else None)
            return root

You can use this code to merge two binary trees by providing the root nodes of the trees t1 and t2 as arguments to the mergeTrees function.

Time and Space Complexity

Understanding the time and space complexity of your code is crucial when working with large datasets or on time-critical applications.

Time Complexity: As mentioned earlier, the time complexity of this solution is O(n + m), where n and m are the numbers of nodes in t1 and t2, respectively.

We traverse both trees simultaneously in a single pass.

Space Complexity: The space complexity is also O(n + m) due to the recursive function calls, which create new tree nodes as they merge the trees.

In the worst case, where t1 and t2 are both non-null, we would have n + m function calls on the call stack.

Reasoning Behind Our Approach

The reasoning behind our approach is that we need to merge two binary trees efficiently while considering all possible cases.

We use a recursive solution to traverse both trees and create a new tree with merged values.

By handling null nodes gracefully and efficiently, we can merge trees of varying shapes and sizes.

Conclusion

In this blog post, we’ve tackled the Merge Two Binary Trees problem on LeetCode, specifically LeetCode Problem 617. We’ve provided a Python solution that efficiently merges two binary trees, considering all possible cases, and explained the code step by step.

If you’re new to coding or want to improve your skills, practicing with LeetCode problems is an excellent way to learn and grow.

We hope this post has been helpful in understanding how to approach and solve this problem.

If you have any questions, suggestions, or comments, please feel free to share

them.

Happy coding!

Question Link

Remember, the best way to learn and improve is to practice.

So, don’t hesitate to try out more coding problems and explore different algorithms.