medium Merge Two Binary Trees

Problem Statement

Given two binary trees, root1 and root2, merge them into a single, new binary tree.

If two nodes from the given trees share the same position, their values should be summed up in the resulting tree. If a node exists in one tree but not in the other, the resulting tree should have a node at the same position with the value from the existing node.

Examples

Example 1:

Trees:

Tree 1:      1            Tree 2:       1
           /   \                      /   \
          3     2                    2     3

Merged:       2
            /   \
           5     5

Justification: The root nodes of both trees have the value 1, so the merged tree's root has a value of 1 + 1 = 2. For the left child, 3 + 2 = 5 and for the right child, 2 + 3 = 5.

Example 2:

Trees:

Tree 1:      5            Tree 2:       3
           /   \                      /   \
          4     7                    2     6

Merged:       8
            /   \
           6    13

Justification: The root nodes have values 5 and 3 respectively. So, the merged tree's root value becomes 5 + 3 = 8. The left child is 4 + 2 = 6 and the right child is 7 + 6 = 13.

Example 3:

Trees:

Tree 1:      2            Tree 2:      2
              \                       /   
               5                     3     

Merged:       4
            /   \
           3     5

Justification: The root nodes have values 2 each, so the merged tree's root value is 2 + 2 = 4. Tree 1 doesn't have a left child, so we take the left child of Tree 2 as it is, which is 3. Similarly, Tree 2 doesn't have a right child, so the merged tree's right child is the same as Tree 1, which is 5.

Example 4:

Trees:

Tree 1:      10           Tree 2:       10
           /    \                     /    \
          5     15                   6     16

Merged:       20
            /    \
           11    31

Justification: The root nodes have the value 10, so they add up to 20 for the merged tree. The left child values add up to 5 + 6 = 11 and the right child values sum up to 15 + 16 = 31.

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -10⁴ <= Node.val <= 10⁴

Solution

The most straightforward approach to solve this problem is to use a recursive algorithm. Start by checking if either of the nodes from the two trees at the current position is null. If so, return the non-null node as it is; if both are null, return null. If both nodes exist, create a new node with the sum of their values.

The next steps are recursive calls. Call the function recursively for the left and right children of the two current nodes and set the left and right children of the new node based on these calls.

1. Base Case Checks:

   • If root1 is null, return root2.
   • If root2 is null, return root1.

2. Node Value Summation: If both root1 and root2 are not null, create a new node with a value equal to the sum of root1 and root2's values.

3. Recursive Calls for Child Nodes:

   • Recursively call mergeTrees for the left children of root1 and root2, and set the left child of the new node to the result of this recursive call.
   • Similarly, recursively call mergeTrees for the right children of root1 and root2, and set the right child of the new node to the result.

4. Return the Merged Node: The new node now represents the merged result of root1 and root2 at this position in the tree. Return this node.

5. Termination: The recursion will terminate once all nodes in both trees have been traversed. The return value of the initial call to mergeTrees will be the root of the newly merged binary tree.

This approach works well because we are addressing every scenario: 1) both nodes are null, 2) one node is null and the other is not, and 3) both nodes exist. By handling these cases, we ensure that the new tree is correctly constructed.

Algorithm Walkthrough

For example, let's take the following example trees: [1, 2, 3, 4, 5] and [1, 2, 3, null, 5]:

Tree 1:      1            Tree 2:       1
           /   \                      /   \
          2     3                    2     3
         / \                          \
        4   5                          5

Merged:
             2            
           /   \   
          4     6  
         / \       
        4   10      

*Here is the visual walkthrough of the algorithm:

1. Start at the Root of Both Trees (1 and 1):

   • Since both roots are not null, create a new node with the sum of both values: 1 + 1 = 2.
   • Recursively merge the left children and right children.

2. Merge Left Children (2 and 2):

   • Both nodes are not null, so create a new node with the sum: 2 + 2 = 4.

3. Merge Left's Left Children (4 and null):

   • Since the second node is null, return the first node (4).

4. Merge Left's Right Children (5 and 5):

   • Both nodes are not null, so create a new node with the sum: 5 + 5 = 10.

5. Merge Right Children (3 and 3):

   • Both nodes are not null, so create a new node with the sum: 3 + 3 = 6.
   • Merge the left children (null and null) and the right children (null and null).
   • Both left and right children are null, so they remain null.

6. Construct the Merged Tree:

   • Now, we construct the merged tree using the new nodes created during the merging process.

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int x) {
//         val = x;
//     }
// }

public class Solution {

  public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    // If one of the nodes is null, return the other node
    if (t1 == null) return t2;
    if (t2 == null) return t1;

    // Create a new node with the sum of values of t1 and t2.
    TreeNode newNode = new TreeNode(t1.val + t2.val);

    // Recursive call for left and right children.
    newNode.left = mergeTrees(t1.left, t2.left);
    newNode.right = mergeTrees(t1.right, t2.right);

    return newNode;
  }

  public static void main(String[] args) {
    // Test the algorithm with given input
    Solution solution = new Solution();

    TreeNode tree1 = new TreeNode(1);
    tree1.left = new TreeNode(2);
    tree1.right = new TreeNode(3);
    tree1.left.left = new TreeNode(4);
    tree1.left.right = new TreeNode(5);

    TreeNode tree2 = new TreeNode(1);
    tree2.left = new TreeNode(2);
    tree2.right = new TreeNode(3);
    tree2.left.right = new TreeNode(5);

    TreeNode mergedTree = solution.mergeTrees(tree1, tree2);

    // Print the merged tree using inorder traversal
    printInOrder(mergedTree);
  }

  // Utility method to print tree using inorder traversal
  public static void printInOrder(TreeNode node) {
    if (node == null) return;
    printInOrder(node.left);
    System.out.print(node.val + " ");
    printInOrder(node.right);
  }
}

Complexity Analysis

• Time Complexity: , where n and m are the numbers of nodes in the first and second trees respectively.
• Space Complexity: , as we're creating a new tree with that many nodes.