Leetcode 617. Merge Two Binary Trees

Merge Two Binary Trees

Leetcode 617. Merge Two Binary Trees : 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 are overlapped while the others are 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 NOT 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.

Approach #1 Using Recursion:

We can traverse both the given trees in a preorder fashion. At every step, we check if the current node exists(isn't null) for both the trees. If so, we add the values in the current nodes of both the trees and update the value in the current node of the first tree to reflect this sum obtained. At every step, we also call the original function mergeTrees() with the left children and then with the right children of the current nodes of the two trees. If at any step, one of these children happens to be null, we return the child of the other tree(representing the corresponding child subtree) to be added as a child subtree to the calling parent node in the first tree. At the end, the first tree will represent the required resultant merged binary tree.


public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}

Time Complexity: O(m) and Space Complexity: O(m)

Time complexity : O(m). A total of m nodes need to be traversed. Here, m represents the minimum number of nodes from the two given trees. Space complexity : O(m). The depth of the recursion tree can go upto m in the case of a skewed tree. In average case, depth will be O(logm).

Approach #2 Iterative Method

In the current approach, we again traverse the two trees, but this time we make use of a stack to do so instead of making use of recursion. Each entry in the stack stores data in the form We start off by pushing the root nodes of both the trees onto the stack. Then, at every step, we remove a node pair from the top of the stack. For every node pair removed, we add the values corresponding to the two nodes and update the value of the corresponding node in the first tree. Then, if the left child of the first tree exists, we push the left child(pair) of both the trees onto the stack. If the left child of the first tree doesn't exist, we append the left child(subtree) of the second tree to the current node of the first tree. We do the same for the right child pair as well. If, at any step, both the current nodes are null, we continue with popping the next nodes from the stack.


public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        Stack < TreeNode[] > stack = new Stack < > ();
        stack.push(new TreeNode[] {t1, t2});
        while (!stack.isEmpty()) {
            TreeNode[] t = stack.pop();
            if (t[0] == null || t[1] == null) {
                continue;
            }
            t[0].val += t[1].val;
            if (t[0].left == null) {
                t[0].left = t[1].left;
            } else {
                stack.push(new TreeNode[] {t[0].left, t[1].left});
            }
            if (t[0].right == null) {
                t[0].right = t[1].right;
            } else {
                stack.push(new TreeNode[] {t[0].right, t[1].right});
            }
        }
        return t1;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

See Video lecture

Leetcode 617. Merge Two Binary Trees

Introduction

The "Merge Two Binary Trees" problem is about merging two binary trees into one. The merge operation takes two trees and merges them node by node. If two nodes overlap, their values are summed, and if only one node exists in one of the trees, the node from the other tree is used.

This problem is commonly used to practice tree traversal techniques and recursive approaches in binary trees.

Problem Statement

Given two binary trees, `root1` and `root2`, merge them into a new binary tree. The merge rule is as follows:

If both nodes are non-null, add them together and set the result as the new value of the merged node.
If one of the nodes is null, the non-null node will be the new node of the merged tree.

Return the merged binary tree. The tree is represented by the following node structure:

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

You are tasked with merging two binary trees using the rules defined above.

Approach

To solve this problem, we can use a recursive depth-first approach. We traverse both trees simultaneously, merging nodes from each tree as we go. The key steps are:

If both nodes are null, return null.
If one of the nodes is null, return the non-null node.
If both nodes are non-null, add their values and recursively merge their left and right children.

This recursive approach ensures that we visit each node in both trees and merge them accordingly.

Algorithm

The algorithm can be broken down into the following steps:

Check if both nodes are null. If so, return null.
If one node is null, return the non-null node.
If both nodes are non-null, create a new node with the sum of the two nodes' values.
Recursively merge the left children of both nodes and assign it to the new node's left child.
Recursively merge the right children of both nodes and assign it to the new node's right child.
Return the newly created node.

This approach ensures that we handle both null and non-null nodes effectively during the traversal and merging process.

Example

Consider the following binary trees:

The merged tree would look like this:

        Merged Tree:
               3
              / \
             4   5
            / \   \
           5   4   7

In the merged tree: - The root node value is 1 + 2 = 3. - The left child node value is 3 + 1 = 4. - The right child node value is 2 + 3 = 5. - The left subtree is merged recursively.

Code Implementation

Below is the Python code to merge two binary trees using a recursive approach:

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

class Solution:
    def mergeTrees(self, root1, root2):
        # If both nodes are null, return null
        if not root1 and not root2:
            return None
        
        # If one of the nodes is null, return the other node
        if not root1:
            return root2
        if not root2:
            return root1
        
        # Create a new node with the sum of both nodes' values
        root = TreeNode(root1.val + root2.val)
        
        # Recursively merge left and right children
        root.left = self.mergeTrees(root1.left, root2.left)
        root.right = self.mergeTrees(root1.right, root2.right)
        
        return root

In this code: - The `mergeTrees` function recursively merges the two trees. - If both nodes are null, it returns null. - If one node is null, it returns the non-null node. - If both nodes are non-null, it creates a new node with the sum of the values and recursively merges the left and right children.

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the larger of the two trees. This is because we visit each node in both trees exactly once.

The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case, for an unbalanced tree, the height will be O(n), resulting in a space complexity of O(n). For a balanced tree, the height will be O(log n), so the space complexity will be O(log n).

Optimized Approach

The current approach is already optimal in terms of time complexity, as we visit each node once. The space complexity depends on the recursion stack, which is determined by the height of the tree.

While the time complexity cannot be further optimized, an iterative approach using a stack or queue could be used to reduce recursion overhead in cases where the tree is very deep.

Time Complexity (Optimized)

The time complexity remains O(n), where n is the number of nodes in the larger of the two trees. The space complexity is O(h), where h is the height of the tree, which can be O(n) in the worst case (for an unbalanced tree) and O(log n) for a balanced tree.

Conclusion

The "Merge Two Binary Trees" problem involves recursively merging two binary trees by adding node values and handling cases where one or both nodes are null. The optimal solution visits each node exactly once, making the time complexity O(n), and the space complexity is O(h), where h is the height of the tree due to the recursion stack.