617. Merge Two Binary Trees
Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 75.5%
Problem Breakdown
The problem requires merging two binary trees into one. If nodes overlap in both trees, their values are summed up. Otherwise, the non-null node is used. The merging process starts from the root nodes of both trees.
Inputs:
- Two binary trees
root1androot2.
Outputs:
- A new binary tree that is the result of merging
root1androot2.
Implicit Constraints or Edge Cases:
- If one tree is empty, return the other tree.
- The number of nodes in both trees ranges from 0 to 2000.
- Node values range from -10^4 to 10^4.
Intuition
A brute-force approach would involve traversing both trees simultaneously and creating a new tree node for each position, summing the values if they overlap. This approach is straightforward but inefficient in terms of space complexity because it creates a new tree instead of modifying one of the existing trees.
The key insight is to perform an in-place merge by recursively updating nodes from root1 with values from root2. If a node in root1 is null, we can directly use the corresponding node from root2.
Approach
We will use a recursive approach to traverse both trees simultaneously. At each step:
- If both nodes are non-null, sum their values and assign it back to
root1. - If one of the nodes is null, return the non-null node.
- Recursively merge the left children and right children of the current nodes.
This approach modifies root1 in place to save space.
Complexity Analysis
- Time Complexity: O(n), where n is the total number of nodes in both trees. We visit each node exactly once.
- Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack. In the worst case, when the tree is skewed, the space complexity can be O(n).
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def mergeTrees(root1: TreeNode, root2: TreeNode) -> TreeNode:
if not root1:
return root2
if not root2:
return root1
# Sum the values of overlapping nodes
root1.val += root2.val
# Recursively merge left children
root1.left = mergeTrees(root1.left, root2.left)
# Recursively merge right children
root1.right = mergeTrees(root1.right, root2.right)
return root1
Edge Cases Handled
- Empty Trees: If either
root1orroot2is null, the function returns the other tree. - Skewed Trees: The recursive approach handles skewed trees efficiently by only using the height of the tree for the recursion stack.