algoadvance

Leetcode 617. Merge Two Binary Trees

Problem Statement

You are given two binary trees. 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.

Clarifying Questions

1. Can we modify the input trees, or must we create a new tree?
   • It’s better to create a new tree if not mentioned otherwise as this avoids altering the input data.
2. What should be done if one of the trees is null?
   • If one of the trees is null, the other non-null tree should be returned as part of the merged tree.
3. Is there a constraint on the height of the trees?
   • No, there are no specific constraints mentioned regarding the height of the trees.

Strategy

1. Use Depth-First Search (DFS) to traverse both trees simultaneously.
2. If both nodes are non-null, sum their values and recursively process their left and right children.
3. If one of the nodes is null, simply use the non-null node as the new node for that position in the merged tree.
4. If both nodes are null, the merged node at that position remains null.
5. Return the root of the merged tree.

Code

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // If either of the trees is null, return the other tree
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }

        // Merge the values of root nodes
        TreeNode merged = new TreeNode(root1.val + root2.val);
        
        // Recursively merge the left and right children
        merged.left = mergeTrees(root1.left, root2.left);
        merged.right = mergeTrees(root1.right, root2.right);

        return merged;
    }
}

Time Complexity

• Time Complexity: O(N), where N is the minimum number of nodes from the two trees. Each node is visited once.
• Space Complexity: O(H), where H is the height of the smaller tree. This is due to the recursive call stack. In the worst case, the height could be the number of nodes (N) if the tree is very unbalanced, but typically O(log N) for a balanced tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?