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.
Tree 1: 1 Tree 2: 2 / \ / \ 3 2 1 3 / \ \ 5 4 7
Merged Tree: 3 / \ 4 5 / \ \ 5 4 7
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
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.
- If both nodes are null, return null.
- If one node is null, return the non-null node.
- If both nodes are not null, add their values and continue the recursion on the left and right children.
- 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
- 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.
- 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.
- If the first tree is empty, return the second tree.
- Initialize a stack and push the root nodes of both trees onto the stack.
- While the stack is not empty, pop a pair of nodes from the stack.
- If one of the nodes is null, continue.
- Sum the values of the two nodes.
- 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.
- Repeat the previous step for the right children.
- 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
- Similar to the recursive approach, O(min(n, m)).
- O(min(n, m)), as in the worst case, the stack may store all nodes of the smaller tree.
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.