Merge Two Binary Trees – Leetcode-617 | Merge Two Binary Trees LeetCode Solution in Java

Binary trees are a fundamental data structure in computer science and programming. They are used to represent hierarchical structures like file systems, family trees, and more. Sometimes, you might need to merge two binary trees to create a new tree that contains all the nodes from both trees. This is a common problem in programming interviews and coding challenges. In this blog post, we’ll explore the LeetCode problem #617 – Merge Two Binary Trees, and we’ll provide a solution in Java.

Problem Statement

LeetCode problem #617 asks us to merge two binary trees and return a new merged tree. The merge rule is as follows:

1. If both trees have a node in the same position, sum the values of the nodes and create a new node with the sum as its value.
2. If only one tree has a node in the current position, create a new node with that node’s value.
3. If neither tree has a node in the current position, the resulting tree should have a null node at that position.

Here’s a visual representation of the problem:

Tree 1                  Tree 2                   Merged Tree
    1                       2                        3
   / \                     / \                      / \
  3   2                   1   3                    4   5
 /                         \   \                    \   \
5                           4   7                    9   7

In the above example, we merge two binary trees, Tree 1 and Tree 2, to get the merged tree. We sum the values at each node, and if a node is missing in one of the trees, we consider it as null.

Approach to Solving the Problem

To solve this problem, we can use a recursive approach. We’ll traverse both trees in a depth-first manner simultaneously, following the merge rules mentioned earlier.

Here’s a step-by-step algorithm to merge two binary trees:

1. If both the current nodes from Tree 1 and Tree 2 are null, return null because there’s nothing to merge at this position.
2. If either of the current nodes is not null, create a new node for the merged tree with the sum of values (or the non-null value).
3. Recursively merge the left subtree and the right subtree of both Tree 1 and Tree 2 and assign the results to the left and right subtrees of the new node created in step 2.
4. Return the merged node as the root of the merged tree.

Let’s implement this algorithm in Java.

Java Solution

Here’s the Java code to solve the problem:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class MergeTwoBinaryTrees {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // If both nodes are null, return null.
        if (root1 == null && root2 == null) {
            return null;
        }

        // Calculate the value for the merged node.
        int mergedValue = (root1 != null ? root1.val : 0) + (root2 != null ? root2.val : 0);

        // Create a new node with the merged value.
        TreeNode mergedNode = new TreeNode(mergedValue);

        // Recursively merge the left subtrees and assign the result to the left child.
        mergedNode.left = mergeTrees(root1 != null ? root1.left : null, root2 != null ? root2.left : null);

        // Recursively merge the right subtrees and assign the result to the right child.
        mergedNode.right = mergeTrees(root1 != null ? root1.right : null, root2 != null ? root2.right : null);

        return mergedNode;
    }
}

In the code above, we define a TreeNode class to represent the nodes of the binary tree. Then, we implement the mergeTrees function, which takes two tree nodes as input and returns the merged tree.

Example

Let’s test our solution with an example:

public static void main(String[] args) {
    // Construct Tree 1
    TreeNode tree1 = new TreeNode(1);
    tree1.left = new TreeNode(3);
    tree1.left.left = new TreeNode(5);
    tree1.right = new TreeNode(2);

    // Construct Tree 2
    TreeNode tree2 = new TreeNode(2);
    tree2.left = new TreeNode(1);
    tree2.left.right = new TreeNode(4);
    tree2.right = new TreeNode(3);
    tree2.right.right = new TreeNode(7);

    MergeTwoBinaryTrees merger = new MergeTwoBinaryTrees();
    TreeNode mergedTree = merger.mergeTrees(tree1, tree2);

    // Print the merged tree
    printTree(mergedTree);
}

public static void printTree(TreeNode root) {
    if (root == null) {
        return;
    }

    System.out.print(root.val + " ");
    printTree(root.left);
    printTree(root.right);
}

Output:

3 4 5 5 4 7

In this example, we construct two binary trees (Tree 1 and Tree 2), merge them using our mergeTrees function, and print the merged tree using the printTree function. The output is as expected, showing the values of the nodes in the merged tree.

Complexity Analysis

The time complexity of our solution is O(N), where N is the total number of nodes in the merged tree. This is because we visit each node once during the traversal.

The space complexity is also O(N) due to the recursive call stack. In the worst case, when the trees are skewed and have N nodes, the call stack can go as deep as N levels.

Conclusion

In this blog post, we explored the LeetCode problem #617 – Merge Two Binary Trees, and we provided a Java solution using a recursive approach. We discussed the problem statement, the algorithm to merge two binary trees, and provided code examples.

Merging binary trees is a common problem in programming interviews and can also be encountered in real-world applications when dealing with hierarchical data structures. Understanding how to traverse and manipulate binary trees is an important skill for any programmer.

I hope this blog post has been helpful in explaining the problem and providing a clear solution. Happy coding!

Thank You!

Read More –

Hollow Inverted Right Triangle Star Pattern Problem | Pattern Printing in Java | Code with Kamlesh – https://kamleshsingad.com/hollow-inverted-right-triangle-star-pattern-problem-and-pattern-printing-in-java/

Symmetric Tree LeetCode | Symmetric Tree LeetCode Solution in Java | Code with Kamlesh- https://kamleshsingad.com/symmetric-tree-leetcode-solution-in-java/

Invert binary Tree | Invert Binary Tree or Mirror Tree LeetCode Solution in Java | Code with Kamlesh – https://kamleshsingad.com/invert-binary-tree-or-mirror-tree-leetcode-solution-in-java/