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:
- Create a new binary tree with an empty root.
- Traverse the first tree in pre-order and add each node to the new tree.
- 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.