Merge Two Binary Trees

"Merge Two Binary Trees" refers to the task of combining two binary trees into a single binary tree. The merging process involves adding corresponding nodes from the two trees together, and if both trees have nodes at the same position, their values are summed up. If one tree has a node at a position where the other tree doesn't, the node from the non-empty tree is copied over to the merged tree. This process continues recursively until all nodes from both trees are merged.

Example: Let's consider an example to merge two binary trees:

Tree 1:
    1
   / \
  3   2
 / \
5   6

Tree 2:
    2
   / \
  1   3
   \   \
    4   7

Merged Tree:
     3
    / \
   4   5
  / \   \
 5   4   7

In this example, we have two binary trees: Tree 1 and Tree 2. We need to merge these two trees to create a new merged tree.

Solution:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def mergeTrees(t1, t2):
    if t1 is None:
        return t2
    if t2 is None:
        return t1

    merged = TreeNode(t1.val + t2.val)
    merged.left = mergeTrees(t1.left, t2.left)
    merged.right = mergeTrees(t1.right, t2.right)

    return merged

# Example usage
t1 = TreeNode(1)
t1.left = TreeNode(3)
t1.right = TreeNode(2)
t1.left.left = TreeNode(5)
t1.left.right = TreeNode(6)

t2 = TreeNode(2)
t2.left = TreeNode(1)
t2.right = TreeNode(3)
t2.left.right = TreeNode(4)
t2.right.right = TreeNode(7)

result = mergeTrees(t1, t2)

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.val, end=' ')
        inorder_traversal(node.right)

print("Merged Tree (inorder traversal):")
inorder_traversal(result)
# Output: 4 5 4 3 5 7

In this solution, we define a TreeNode class to represent the nodes of the binary tree. We then define the mergeTrees function that takes two binary tree nodes (t1 and t2) as input and returns the merged binary tree.

The merge process is performed recursively. At each step, we create a new node in the merged tree with the sum of the values from t1 and t2. We then recursively merge the left and right subtrees of t1 and t2, assigning them to the left and right children of the merged node, respectively.

The time complexity of this solution is O(n), where n is the total number of nodes in the merged tree. Since we visit each node once, the time complexity is linear with respect to the number of nodes. The space complexity is also O(n) in the worst case, as the recursion can go as deep as the height of the merged tree.