algoadvance

You are given two binary trees root1 and root2. Imagine that when you put one of them to cover the other, some nodes of the two trees overlap while the others do not. You need to merge the two trees 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.

Return the merged tree.

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

Example:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Clarifying Questions

  1. Input Format:
    • Are the inputs given as arrays that represent the level order traversal of the trees or as actual TreeNode objects?
      • Typically, they will be given as TreeNode objects.
  2. Tree Structure:
    • Can the trees be of different sizes and shapes?
      • Yes, the trees can be different in both size and shape.
  3. Node Values:
    • Can the node values be negative or zero?
      • Yes, node values can be any integer, including negative and zero.
  4. Constraints:
    • Do we need to handle any special cases (like both trees being empty)?
      • Yes, the algorithm should handle the case where one or both trees are empty.

Strategy

We will use a recursive approach to solve this problem. The recursive function will handle the following scenarios:

  1. Both nodes are non-null: Add the values and recursively merge both left and right children.
  2. One of the nodes is null: Use the non-null node as the result node.
  3. Both nodes are null: Return null.

The base cases for the recursion handle scenarios where at least one of the nodes is null.

Code

Here’s the Python code to merge two binary trees:

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

def mergeTrees(t1: TreeNode, t2: TreeNode) -> TreeNode:
    if not t1:
        return t2
    if not t2:
        return t1
    
    merged = TreeNode(t1.val + t2.val)
    merged.left = mergeTrees(t1.left, t2.left)
    merged.right = mergeTrees(t1.right, t2.right)
    
    return merged

Time Complexity

The time complexity of this approach is O(N), where N is the total number of nodes in the smaller tree. This is because we visit each node exactly once.

The space complexity is O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (completely unbalanced tree), H can be as large as N. However, in the best case (completely balanced tree), H will be log(N).

Try our interview co-pilot at AlgoAdvance.com