Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Merge Two Binary Trees

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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
A

Anonymous

· 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

Reading Progress

0%

Vote for new content