// 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 node1 = q1.poll();
            TreeNode node2 = q2.poll();
            TreeNode nodeMerged = qMerged.poll();

            if (node1.left != null && node2.left != null) {
                nodeMerged.left = new TreeNode(node1.left.val + node2.left.val);
                q1.offer(node1.left);
                q2.offer(node2.left);
                qMerged.offer(nodeMerged.left);
            } else if (node1.left != null) {
                nodeMerged.left = node1.left;
            } else if (node2.left != null) {
                nodeMerged.left = node2.left;
            }

            if (node1.right != null && node2.right != null) {
                nodeMerged.right = new TreeNode(node1.right.val + node2.right.val);
                q1.offer(node1.right);
                q2.offer(node2.right);
                qMerged.offer(nodeMerged.right);
            } else if (node1.right != null) {
                nodeMerged.right = node1.right;
            } else if (node2.right != null) {
                nodeMerged.right = node2.right;
            }
        }

        return merged; 
    }
}