Merge Two Binary Trees

Merging Two Binary Trees

The Problem Statement

You are presented with two binary trees. Your task is to merge these trees into a single, new binary tree.

The Overlap Rule

Here's the catch: some nodes in these two trees may overlap when you try to put them together. When that happens, the new node's value in the merged tree will be the sum of the overlapping nodes. For instance, consider the right leaf node in Tree 1 with a value of 2 and the right node in Tree 2 with a value of 3. In the merged tree, the corresponding node would have a value of 5 (2 + 3).

The No-Overlap Rule

If nodes don't overlap, the node value from the existing tree is simply carried over into the new tree.

An Example to Illuminate

Here's a quick example to make this more concrete:

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

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

Boilerplate Code

You can assume that the nodes in the tree are defined as follows in JavaScript:

function Node(val) {
  this.val = val;
  this.left = this.right = null;
}

Constraints and Expectations

• Both trees will contain no more than 100,000 nodes.
• Node values will always be integers and fall in the range -1,000,000,000 to 1,000,000,000.
• Aim for a time complexity of (O(m+n)), where (m) and (n) are the number of nodes in each of the binary trees, respectively.

Your task is to start merging from the root nodes of both trees and produce a new tree that satisfies the above conditions.

```js
function Node(val) {
  this.val = val;
  this.left = this.right = null;
}

function mergeTwoBinaryTrees(tree1, tree2) {
  // Fill in this method
  return tree1;
}
```

Unveiling the Approach: Merging Binary Trees

Step 1: The Simple Case - Merging Root Nodes

Before diving into the complexities of merging full-fledged binary trees with all their branches and leaves, let's start simple. We'll consider the most basic case: two trees each containing only a root node.

Here's the example we'll work through:

  1st Tree         2nd Tree         Merged Tree       
      3               1                  4               

The Strategy for Merging Root Nodes

1. Check for Empty Trees: First, ensure that neither of the root nodes is null.
2. Sum the Values: If both roots exist, sum their values to create a new root node for the merged tree.
3. Create the Merged Root: Instantiate a new node with the sum as its value.

Code Snippet for Merging Root Nodes

Here's how you would implement these steps.

Great! We've successfully merged two single-node trees. But what happens when these trees have children?

```js
function Node(val) {
  this.val = val;
  this.left = this.right = null;
}

function mergeTrees(root1, root2) {
  // Check for empty trees
  if (!root1) return root2;
  if (!root2) return root1;

  // Sum the root nodes' values
  let sum = root1.val + root2.val;

  // Create the merged root
  let mergedRoot = new Node(sum);

  return mergedRoot;
}

// Create individual root nodes for 1st and 2nd trees
let root1 = new Node(3);
let root2 = new Node(1);

// Merge and get the new root
let mergedRoot = mergeTrees(root1, root2);
console.log(`Merged Root Value: ${mergedRoot.val}`);  // Output should be 4
```
```java
public class Node {
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    public static Node mergeTrees(Node root1, Node root2) {
        // Check for empty trees
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        // Sum the root nodes' values
        int sum = root1.val + root2.val;

        // Create the merged root
        Node mergedRoot = new Node(sum);

        return mergedRoot;
    }

    public static void main(String[] args) {
        // Create individual root nodes for 1st and 2nd trees
        Node root1 = new Node(3);
        Node root2 = new Node(1);

        // Merge and get the new root
        Node mergedRoot = mergeTrees(root1, root2);
        System.out.println("Merged Root Value: " + mergedRoot.val);  // Output should be 4
    }
}
```
```python
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def merge_trees(root1, root2):
    # Check for empty trees
    if not root1:
        return root2
    if not root2:
        return root1
    
    # Sum the root nodes' values
    sum_val = root1.val + root2.val
    
    # Create the merged root
    merged_root = Node(sum_val)
    
    return merged_root

# Create individual root nodes for 1st and 2nd trees
root1 = Node(3)
root2 = Node(1)

# Merge and get the new root
merged_root = merge_trees(root1, root2)
print(f"Merged Root Value: {merged_root.val}")  # Output should be 4
```
```cpp
#include <iostream>

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(NULL), right(NULL) {}
};

Node* mergeTrees(Node* root1, Node* root2) {
    // Check for empty trees
    if (!root1) return root2;
    if (!root2) return root1;

    // Sum the root nodes' values
    int sum = root1->val + root2->val;

    // Create the merged root
    Node* mergedRoot = new Node(sum);

    return mergedRoot;
}

int main() {
    // Create individual root nodes for 1st and 2nd trees
    Node* root1 = new Node(3);
    Node* root2 = new Node(1);

    // Merge and get the new root
    Node* mergedRoot = mergeTrees(root1, root2);
    std::cout << "Merged Root Value: " << mergedRoot->val << std::endl;  // Output should be 4

    return 0;
}
```
```csharp
using System;

public class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class Program {
    public static Node MergeTrees(Node root1, Node root2) {
        // Check for empty trees
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        // Sum the root nodes' values
        int sum = root1.val + root2.val;

        // Create the merged root
        Node mergedRoot = new Node(sum);

        return mergedRoot;
    }

    static void Main(string[] args) {
        // Create individual root nodes for 1st and 2nd trees
        Node root1 = new Node(3);
        Node root2 = new Node(1);

        // Merge and get the new root
        Node mergedRoot = MergeTrees(root1, root2);
        Console.WriteLine("Merged Root Value: " + mergedRoot.val);  // Output should be 4
    }
}
```
```go
package main

import "fmt"

type Node struct {
	val   int
	left  *Node
	right *Node
}

func mergeTrees(root1 *Node, root2 *Node) *Node {
	// Check for empty trees
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}

	// Sum the root nodes' values
	sum := root1.val + root2.val

	// Create the merged root
	mergedRoot := &Node{val: sum}

	return mergedRoot
}

func main() {
	// Create individual root nodes for 1st and 2nd trees
	root1 := &Node{val: 3}
	root2 := &Node{val: 1}

	// Merge and get the new root
	mergedRoot := mergeTrees(root1, root2)
	fmt.Printf("Merged Root Value: %d\n", mergedRoot.val)  // Output should be 4
}
```

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.

Complete the sentence. The merge rule is: if two nodes overlap, the resultant node is the _________ of the two nodes.

True or False? The merging step does not have to start from the root nodes of both trees.

Visualizing the Merging Process

The picture truly is worth a thousand words. In this diagram, we see Tree 1 with a root node of 3 and Tree 2 with a root node of 1. As per our observation #1—"Roots Merge"—we combine these roots to create a new root for the merged tree, which has a value of (3 + 1 = 4).

The Steps in the Process

1. Start at the Roots: We begin with the root nodes of both Tree 1 and Tree 2. These are 3 and 1, respectively.

2. Merge the Roots: We add the values of these root nodes together. (3 + 1 = 4)

3. Create the Merged Root: We then use this sum to create the root node of our new, merged tree.

```js
/*
  1st Tree            2nd Tree           Merged Tree            
      3                  1                    4   
     / \                / \                  / \        
    1                  3                    4        
*/
```

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.

How many parameters does the merge tree function need to perform a merger?

Which of the following is the correct order of visiting nodes for a pre-order traversal?

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:

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

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.

Traversal is the key

Since we started we'll need to eventually return a merged root, let's go with an pre-order traversal. Pseudocode as follows:

```js
function preOrder(tree1, tree2) {
  if (tree1 == null) {
    return tree2;
  }
  if (tree2 == null) {
    return tree1;
  }
  return tree1.val + tree2.val;

  // Do the above on both of their left children
  preOrder(tree1.left, tree2.left)

  // Do the above on both of their right children
  preOrder(tree1.right, tree2.right)
}
```

Applying this to the problem at hand, doSomeOperation() for us would mean checking the currently investigated node position at both the first and second trees, and deciding what to return.

But what do we need to get back? Here's an operation that might work given our examples:

```js
if (tree1 == null) {
  return tree2;
}
if (tree2 == null) {
  return tree1;
}
tree1.val = tree1.val + tree2.val
return tree1;
```

The above code isn't exactly right though-- we're not returning a sum of the two values after checking for null on both, but rather we should be returning a merged node object. To save space, if there are values at both nodes, let's just add them onto the first tree and simply return it.

Arrange the following instructions into the correct order to merge two binary trees recursively:

This needs to be done at every recurrence as we traverse through the trees. However, the traversal needs to be done before we return tree1-- the intuition being that we need to adjust the children of each node before we can give it back. In other words, we should write the merge results on the first tree before presenting it back in our method.

```js
function mergeTwoBinaryTrees(tree1, tree2) {
  if (tree1 == null) {
    return tree2;
  }
  if (tree2 == null) {
    return tree1;
  }
  tree1.val += tree2.val

  tree1.left = mergeTwoBinaryTrees(tree1.left, tree2.left);
  tree1.right = mergeTwoBinaryTrees(tree1.right, tree2.right);

  return tree1;
}
```

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.

What is the time complexity of the recursive tree merger algorithm?

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.