Merge Binary trees and sum nodes

Problem

Write an algorithm that takes 2 trees as input and returns a tree which is the result of merging the 2 input trees, such that each node is the sum of the values of the corresponding nodes in the input tree. If only one of the 2 input trees has a node in the given position, then the output node will have a node with this value in the given position.

Example:

Input:

          4               5
        /   \           /
       5     4         8
        \               \
         1               3


Output:

          9
        /  \
      13    4
        \
         4

Approach

This intuition for this problem is to realize that it can be solved by traversing both trees in any order and return a new node that is the result of merging the 2 input nodes. By doing the recursion properly the algorithm returns the root of a new tree.

Solution

The recursive solution to this problem (note that this problem can be solved in the same way using an iterative solution) is to take as input 2 nodes, create a new node with value equal to the sum of the input nodes, and then recursively call the function on the left and right children to populate the left and right subtrees, and then return the node itself. The tricky part of the algorithm is to manage the edge cases, like when the left, right or both nodes are null. Time complexity of the solution is O(M) where M is the min size of the 2 input trees.

BTNode mergeTrees(BTNode root1, BTNode root2) {
    if (root1 == null) {
        return root2;
    }

    if (root2 == null) {
        return root1;
    }

    BTNode node = new BTNode(root1.data + root2.data);
    node.left = mergeTrees(root1.left, root2.left);
    node.right = mergeTrees(root1.right, root2.right);
    return node;
}