Unveiling the Approach: Merging Binary Trees

The Human Approach to Merging Trees

Imagine you have two different trees. To combine them into one tree, you'd naturally start by looking at the top piece of each puzzle—the root. You'd combine these roots to create a new root for the merged tree.

Then, you'd proceed down each branch, combining corresponding pieces (nodes) from each tree. If a branch exists in one tree but not the other, you'd simply include the existing branch in the new tree. If a branch exists in both trees, you'd combine them to form a new branch.

Running Through Examples to Identify Patterns

Example 1

• Tree 1: A single node with value 3
• Tree 2: A single node with value 1
• Merged Tree: A single node with value (3 + 1 = 4)

Example 2

• Tree 1:
  • Root: 3
  • Left child: 5
• Tree 2:
  • Root: 1
  • Right child: 4
• Merged Tree:
  • Root: (3 + 1 = 4)
  • Left child: 5 (from Tree 1)
  • Right child: 4 (from Tree 2)

Example 3

• Tree 1:
  • Root: 2
  • Left child: 3
  • Right child: 4
• Tree 2:
  • Root: 1
  • Left child: 4
  • Right child: 5
• Merged Tree:
  • Root: (2 + 1 = 3)
  • Left child: (3 + 4 = 7)
  • Right child: (4 + 5 = 9)

Observations

1. Roots Merge: The root of the merged tree is the sum of the roots of the individual trees.
2. Branching Logic: If a node exists in one tree but not in the other, the node from the existing tree is included in the merged tree.
3. Recursive Nature: The process for merging the children of two nodes looks suspiciously similar to the process for merging the roots. This suggests a recursive solution.

Armed with these observations, we can confidently proceed to code our brute-force solution.

Moving Down to the Left Child Node

Excellent! We've successfully merged the root nodes. Now, it's time to move on to the children nodes, starting with the left child. Just as we merged the root nodes, we'll use the same strategy for the children nodes.

A Step-by-Step Look

1. Locate the Left Children: Per the current example, let's assume that Tree 1 has a left child with a value of 1, and Tree 2 has a left child with a value of 3.

2. Merge the Left Children: As with the roots, we sum the values of these left children nodes. (1 + 3 = 4)

3. Create the Merged Left Child: This sum becomes the value of the new left child node in our merged tree.

Result of the Operation

By following these steps, we end up with a merged tree that has a root node of 4 and a left child node of 4.

The Recursive Nature

What's nice about this process is its inherently recursive nature. Once we've figured out how to merge the root and one set of children nodes, we can apply the same logic to all subsequent layers of the tree. This sets us up perfectly for the coding phase, where recursion will help us elegantly navigate and merge the trees.

Identifying the Traversal Pattern

The pattern you're seeing is indicative of a tree traversal algorithm. Specifically, what we're doing can be modeled as a Preorder Traversal.

Why Preorder Traversal?

In preorder traversal, we visit the root first, then traverse the left subtree, and finally the right subtree. This is exactly what we're doing while merging the trees:

1. Visit the Root: Merge the root nodes of both trees.
2. Traverse the Left Subtree: Merge the left subtrees of both trees.
3. Traverse the Right Subtree: Merge the right subtrees of both trees.

Here’s how the Preorder Traversal skeleton code might look in JavaScript:

1function preOrder(node) {
2  if (!node) return;
3  // Perform some operation on the current node (like merging)
4  preOrder(node.left);  // Traverse the left subtree
5  preOrder(node.right); // Traverse the right subtree
6}

Adaptation for Merging

To adapt this for merging, we would:

1. Sum the current nodes from both trees and create a new node in the merged tree.
2. Recursively perform this operation for left and right children.

The skeleton code for Preorder Traversal gives us a good framework to build upon for our merging function.

Understanding Time Complexity: $O(m+n)$

You've got it spot on! The time complexity of $O(m+n)$ perfectly captures the nature of this problem.

Why $O(m+n)$?

1. Every Node Visited Once: In the process of merging, each node in both trees is visited exactly once.
2. Single Operation Per Node: At each visit, we perform a constant amount of work (i.e., summing node values and creating a new node).

Considering that there are $m$ nodes in the first tree and $n$ nodes in the second tree, it's quite straightforward to conclude that the overall time complexity is $O(m+n)$.

The Intuition

Think of it like two separate lists that you need to merge into one. You have to look at each element at least once in both lists to accomplish this. In our case, the lists are just a bit more complex, structured as binary trees. But the fundamental idea remains the same: you have to touch every node at least once.

One Pager Cheat Sheet

• The sum of overlapping nodes is used to create the merged tree, while nodes that do not overlap remain unchanged, within the constraints of O(m+n) time complexity and -1000000000 to 1000000000 for node values.
• We can merge trees with just root nodes to gauge how we'd perform this exercise for trees with children.
• We can brute force solve a problem by visualizing how a human would do it, and running through examples to find patterns.
• The merge rule states that when two nodes overlap, their attributes and properties are combined summarily to form a resultant node.
• The merge rule allows any two overlapping nodes to be combined, so it does not have to start from the root nodes of both trees.
• We could sum up the node values of two trees, by processing at the root of each one, and then checking for left and right children, according to rule #2.
• We scan the tree from left to right and sum up the values we find between each node, returning 4 from the root's left child.
• The merge tree function combines the two tree nodes by adding the two elements within them together to get the result.
• The algorithm of pre-order traversal is a Depth-First Search which visits the nodes of a tree in the root, left, right order.
• We can traverse both trees simultaneously and check their values at each step to create a pattern.
• The pre-order traversal technique is the key to returning a merged root.
• Checking the node position of the currently investigated element at the first and second trees using doSomeOperation() can determine what to return.
• We should merge the two nodes by adding their values onto the first tree, and then simply return it.
• The process of merging two binary trees recursively begins with a pre-order traversal of the first tree, checking the nodes of both trees, and then updating the first tree with the sum of their values before continuing with the subtrees.
• We should traverse both trees before returning tree1, writing the merge results in the process.
• We traverse through both binary trees at once with a time complexity of O(m+n), allowing us to process one node of each tree per iteration.
• The time complexity of the recursive tree merger algorithm is O(n), as it only traverses the larger tree, resulting in a worst-case of O(n) nodes.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

    print("Nice job, 2/2 tests passed!")

# class Node:

#   def __init__(val):

#     this.val = val

#     this.left = None

#     self.right = None

​

​

def merge_two_binary_trees(tree1, tree2):

    if tree1 is None:

        return tree2

​

    if tree2 is None:

        return tree1

​

    tree1.val += tree2.val

    tree1.left = merge_two_binary_trees(tree1.left, tree2.left)

    tree1.right = merge_two_binary_trees(tree1.right, tree2.right)

    return tree1

​

​

# Node definition

class Node:

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

​

​

# Regular binary trees

tree1 = Node(4)

tree1.left = Node(1)

tree1.right = Node(3)

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.