Leetcode – Merge Two Binary Trees Solution in Python

Spread the love

Introduction

In this article, we will explore a popular problem from Leetcode, which is known as “Merge Two Binary Trees”. This problem is an interesting and fundamental algorithm problem that allows us to test our understanding of binary trees and recursion. We will discuss the problem statement, different approaches to solving it, analyze their complexity, and walk through Python code examples.

Problem Statement (Leetcode #617)

Given two binary trees and 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 them 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 non-null node will be used as the node of the new tree.

Example:

Input:

Tree 1:       1           Tree 2:       2

             / \                        / \

            3   2                      1   3

           /                            \   \

          5                              4   7

Output:

Merged Tree: 3

             / \

            4   5

           / \   \

          5   4   7

Note:

The merging process must start from the root nodes of both trees.

Definition for a binary tree node:

In Python, a binary tree node can be defined using a class as follows:

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

Solution Approaches

1. Recursive Approach

The most intuitive approach to solving this problem is to use recursion. The basic idea is to traverse both trees in parallel and recursively merge corresponding nodes.

Algorithm:

  1. If both nodes are null, return null.
  2. If one node is null, return the non-null node.
  3. If both nodes are not null, add their values and continue the recursion on the left and right children.
  4. Return the merged tree.
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:
            return t2
        if not t2:
            return t1
        
        t1.val += t2.val
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)
        
        return t1

Time Complexity:

  • O(min(n, m)), where n and m are the number of nodes in the first and second trees, respectively. This is because we need to traverse each node once.

Space Complexity:

  • O(min(h1, h2)), where h1 and h2 are the heights of the first and second trees, respectively. This represents the maximum recursion depth.

2. Iterative Approach

An alternative to the recursive approach is to use iteration. We can use a stack to simulate the recursive calls.

Algorithm:

  1. If the first tree is empty, return the second tree.
  2. Initialize a stack and push the root nodes of both trees onto the stack.
  3. While the stack is not empty, pop a pair of nodes from the stack.
  4. If one of the nodes is null, continue.
  5. Sum the values of the two nodes.
  6. If the left child of the first node is null, set it to the left child of the second node. Otherwise, push the left children of both nodes onto the stack.
  7. Repeat the previous step for the right children.
  8. Return the merged tree.
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:
            return t2
        
        stack = [(t1, t2)]
        
        while stack:
            n1, n2 = stack.pop()
            if not n1 or not n2:
                continue
            
            n1.val += n2.val
            
            if not n1.left:
                n1.left = n2.left
            else:
                stack.append((n1.left, n2.left))
                
            if not n1.right:
                n1.right = n2.right
            else:
                stack.append((n1.right, n2.right))
        
        return t1

Time Complexity:

  • Similar to the recursive approach, O(min(n, m)).

Space Complexity:

  • O(min(n, m)), as in the worst case, the stack may store all nodes of the smaller tree.

Conclusion

In this article, we discussed two approaches to solving the “Merge Two Binary Trees” problem on LeetCode using Python. The recursive approach is more concise and easier to understand, while the iterative approach avoids the overhead of recursive calls. It is essential to be comfortable with both approaches, as different problems might favor one approach over the other.

Leave a Reply