How do you solve Merge Two Binary Trees on LeetCode?

Merge Two Binary Trees (LeetCode #617) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Merging trees requires careful handling of null nodes.

What is the brute force solution for Merge Two Binary Trees?

The brute force approach for Merge Two Binary Trees is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves traversing both trees simultaneously and checking each node. If both nodes exist, we sum their values; if only one exists, we take that node. This approach is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Merge Two Binary Trees?

Merge Two Binary Trees uses the following concepts: Tree, Depth-First Search, Breadth-First Search, Binary Tree. The recommended patterns to study are: Recursion, Tree Traversal.

What are the interview tips for Merge Two Binary Trees?

Always clarify the problem statement and constraints with the interviewer. Think aloud while coding to show your thought process. Test your solution with edge cases, such as empty trees.

What are common mistakes when solving Merge Two Binary Trees?

Forgetting to check for null nodes, leading to null pointer exceptions. Not understanding the base case in recursion.

#617

Merge Two Binary Trees

Easy

TreeDepth-First SearchBreadth-First SearchBinary TreeRecursionTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal solution uses recursion to traverse both trees simultaneously, merging nodes as we go. This approach is efficient because it only visits each node once, leading to a linear time complexity.

⚙️

Algorithm

5 steps

1Step 1: If both nodes are null, return null.
2Step 2: If one node is null, return the other node.
3Step 3: Create a new node with the sum of both nodes' values.
4Step 4: Recursively merge the left children of both nodes.
5Step 5: Recursively merge the right children of both nodes.

solution.py18 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8def mergeTrees(root1, root2):
9    if not root1 and not root2:
10        return None
11    if not root1:
12        return root2
13    if not root2:
14        return root1
15    merged = TreeNode(root1.val + root2.val)
16    merged.left = mergeTrees(root1.left, root2.left)
17    merged.right = mergeTrees(root1.right, root2.right)
18    return merged

ℹ

Complexity note: The time complexity is linear because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1Merging trees requires careful handling of null nodes.
2Recursion is a powerful tool for tree traversal.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.