[LeetCode] #617: Merge Two Binary Trees

Problem:

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 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.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

---

Process:

Objective: Return the root node of the merged tree

Constraints:
1. The number of nodes in both trees is in the range [0, 2000].
2. -10^4 <= Node.val <= 10^4

Edge Cases:
1. root1 is an empty Node
2. root2 is an empty Node

---

Solution:

Attempt #1: Iterative Merge to tree1~~

• Time Complexity: O(n), where n is the number of node of tree1
• Space Complexity: O(n)

Logic behind this decision:
1. I did not want to create an extra tree which will take up at least another n space. Therefore, I decided to merge to tree1.

How it works
1. If both tree1 node and tree2 node are present at a certain position, I've added the values
2. If tree1 node is not present, I simply replaced it with tree2 node (which is not added to the call stack)
3. If tree2 node is not present, tree1 node is preserved (which is not added to the call stack)
*Nodes are added to callstack(stack1 and stack2) only when tree1 node and tree2 node are both present at a certain position.

def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        stack = [(root1, root2)]
        
        # When either root1 or root2 is None
        if not root1:
            return root2
        elif not root2:
            return root1
        
        # Iterating through the tree
        while stack:
            node1, node2 = stack.pop()
            node1.val += node2.val
            
            if node1.right and node2.right:
                # Only Appending when both node1.right and node2.right are present
                stack.append((node1.right, node2.right))
            elif node2.right:
                # Replacing node2.right with node2.right since node1.right is None
                node1.right = node2.right
            
            if node1.left and node2.left:
                # Only Appending when both node1.left and node2.left are present
                stack.append((node1.left, node2.left))
            elif node2.left:
                # Replacing node1.left with node2.left since node1.left is None
                node1.left = node2.left
            
        return root1

Limitations:
1. The code is a little verbose compared to using recursion.

---

LeetCode Question #617