Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Merge Two Binary Trees (medium)

Problem Statement

Given two binary trees, root1 and root2, merge them into a single, new binary tree.

If two nodes from the given trees share the same position, their values should be summed up in the resulting tree. If a node exists in one tree but not in the other, the resulting tree should have a node at the same position with the value from the existing node.

Examples

Example 1:

Trees:

Tree 1:      1            Tree 2:       1
           /   \                      /   \
          3     2                    2     3

Merged:       2
            /   \

.....

.....

.....

Like the course? Get enrolled and start learning!
Run Qi Jack Li

Run Qi Jack Li

· 2 years ago

Time Complexity:

The goal of merging two binary trees involves visiting every node in both trees where nodes exist. Therefore, we need to account for all nodes in the larger of the two trees (t1 and t2), not the smaller.

If one tree is smaller than the other and does not reach the depth of the other tree, we still traverse down the structure of the larger tree, filling in nodes as needed. Hence, the time complexity is determined by the larger tree, or O(max(m, n)), not O(min(m, n)).

Space Complexity:

The space complexity also depends on the depth of the recursion (i.e., the height of the deeper tree) and the total nodes in the new merged tree.

Recursive Stack: If k is the height of the deeper tree between t1 and t2, the recursive stack will go as deep a

Show 1 reply
D

Davide Pugliese

· 2 years ago

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int x) {
//         val = x;
//     }
// }
import java.util.*;
public class Solution {

    public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        // ToDo: Write Your Code Here.
       
        if (t1 == null && t2 == null) return null;
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        
        Deque<TreeNode> q1 = new ArrayDeque<>();
        Deque<TreeNode> q2 = new ArrayDeque<>();
        Deque<TreeNode> qMerged = new ArrayDeque<>();

        TreeNode merged = new TreeNode(t1.val + t2.val);
        q1.offer(t1);
        q2.offer(t2);
        qMerged.offer(merged);

        while (!q1.isEmpty() || !q2.isEmpty()) {
            TreeNode n
Aravind Badiger

Aravind Badiger

· 2 years ago

We could do it without creating new node, but adding the values into one tree from other

Show 1 reply
P P

P P

· 4 months ago

TC should be O(max(n, n)) not O(min(n, n))