merge two binary tree

Merging Two Binary Trees#

If you have two binary trees and want to merge them into one, you can do so by following these steps:

1. Create a new binary tree with an empty root.
2. Traverse the first tree in pre-order and add each node to the new tree.
3. Traverse the second tree in pre-order and add each node to the new tree.

Here is the code for merging two binary trees in Python:

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        
def merge_trees(t1, t2):
    if not t1:
        return t2
    if not t2:
        return t1
    t1.val += t2.val
    t1.left = merge_trees(t1.left, t2.left)
    t1.right = merge_trees(t1.right, t2.right)
    return t1

t1 = Node(1)
t1.left = Node(3)
t1.right = Node(2)
t1.left.left = Node(5)

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

merged_tree = merge_trees(t1, t2)

In this implementation, we traverse both trees in pre-order and add the values of corresponding nodes. If both nodes are not None, we add their values and recursively call the function on their left and right subtrees. If one of the nodes is None, we return the other node. Once we have merged the two trees, we return the root of the merged tree.

Another way to merge two binary trees is to perform a breadth-first search and add nodes level by level. Here is the code for this approach:

from collections import deque

def merge_trees_bfs(t1, t2):
    if not t1:
        return t2
    if not t2:
        return t1
    q = deque([(t1, t2)])
    while q:
        n1, n2 = q.popleft()
        n1.val += n2.val
        if not n1.left and n2.left:
            n1.left = Node(0) # add dummy node
        if not n1.right and n2.right:
            n1.right = Node(0) # add dummy node
        if n1.left and n2.left:
            q.append((n1.left, n2.left))
        if n1.right and n2.right:
            q.append((n1.right, n2.right))
    return t1

merged_tree = merge_trees_bfs(t1, t2)

In this implementation, we use a queue to keep track of corresponding nodes in both trees. We add a dummy node if one of the nodes is None, to ensure that both nodes have left and right children. We continue this process until we have traversed all nodes in both trees, and return the root of the merged tree.