algoadvance

Leetcode 617. Merge Two Binary Trees Sure! Let’s break down the problem step-by-step.

Problem Statement

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 overlap while others do not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum their values as the new value of the merged node. Otherwise, the non-null node will be used as the node of the new tree.

Return the merged tree.

Example:

Input: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
         3
        / \
       4   5
      / \   \ 
     5   4   7

Clarifying Questions

1. Input constraints?
   • Are the given binary trees always valid? (Yes, assume they are always valid binary trees)
2. Handling edge cases?
   • What happens if one or both trees are empty?
     • If both trees are empty, return nullptr.
     • If one tree is empty, return the other tree.

Strategy

1. Define a function mergeTrees that accepts the roots of the two trees.
2. Recursively merge the trees:
   • If one of the nodes (from either tree) is null, return the other node.
   • Create a new tree node whose value is the sum of the values of the input nodes.
   • Recur for the left children and right children.
   • Return the new tree node.
3. The base case for the recursion is when either of the nodes is null.

Time Complexity

• Time Complexity: (O(N)), where (N) is the total number of nodes in both trees, since we traverse as many nodes as exist in the larger tree.
• Space Complexity: (O(H)), where (H) is the height of the recursion stack. In the worst case, this is the height of the larger tree. In the average case, for balanced trees, this is (O(\log N)).

Code

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) return t2;
        if (t2 == nullptr) return t1;

        TreeNode* merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);
        return merged;
    }
};

// Helper function to print the tree (in-order traversal)
void printTree(TreeNode* node) {
    if (node == nullptr) {
        return;
    }
    printTree(node->left);
    std::cout << node->val << " ";
    printTree(node->right);
}

int main() {
    // Create test trees
    TreeNode* tree1 = new TreeNode(1);
    tree1->left = new TreeNode(3);
    tree1->right = new TreeNode(2);
    tree1->left->left = new TreeNode(5);

    TreeNode* tree2 = new TreeNode(2);
    tree2->left = new TreeNode(1);
    tree2->right = new TreeNode(3);
    tree2->left->right = new TreeNode(4);
    tree2->right->right = new TreeNode(7);

    // Merge trees
    Solution s;
    TreeNode* mergedTree = s.mergeTrees(tree1, tree2);

    // Print the merged tree
    std::cout << "Merged Tree: ";
    printTree(mergedTree);  // Expected output: 5 4 4 3 5 7

    return 0;
}

This code merges the two binary trees as described and prints the merged tree using an in-order traversal to verify the solution.

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?