617. Merge Two Binary Trees

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Problem Description

You are asked to merge two binary trees in such a way that if two nodes from the two trees occupy the same position, their values are summed together to create a new node in the resulting binary tree. If at any position, only one of the trees has a node, the resulting tree should have a node with that same value. To merge the trees, you must start from their root nodes and continue merging the subtrees recursively following the same rule.

Flowchart Walkthrough

In order to determine the best approach for solving LeetCode problem 617, "Merge Two Binary Trees," we can utilize the provided algorithm flowchart. Here's how you would navigate through the flowchart to determine the appropriate algorithm to use:

First, let's analyze the problem according to the algorithm flowchart which you can view here:

Is it a graph?

Yes: A binary tree is a specific type of graph.

Is it a tree?

Yes: The structure in the problem is explicitly mentioned as a binary tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: Although a tree is inherently a DAG, the problem is specifically about tree manipulation (tree merging), not about properties or algorithms specific to DAGs.

Since 'tree' leads to using 'DFS' in the flowchart:

The merging process of two binary trees can be efficiently handled using Depth-First Search. Each node in one tree must be merged with the corresponding node in the other tree (if it exists). DFS allows visiting each node in both trees simultaneously and merging them as needed.

Conclusion: Using the flowchart, Depth-First Search (DFS) is suggested for merging two binary trees since it efficiently allows traversal and manipulation of tree data structures.

Intuition

To merge the two given binary trees, the solution employs a recursive approach. Each recursive call is responsible for handling the merging of two nodes – one from each of the trees. The first step is to determine what to do if one or both of the nodes being merged are null. If one of the nodes is null, the other node (which is not null) can be used directly in the merged tree since there's nothing to merge. If both nodes are null, the merged node is also null.

When both nodes are not null, a new node is created with a value that is the sum of the two nodes' values. Following that, the recursion is applied to both the left and the right children of the nodes being merged to handle the full depth of the trees. Thus, the process creates a new tree that is the result of merging the input trees by summing the overlapping nodes and copying the non-overlapping nodes.

Merging goes as deep as the deepest tree, and each level of recursion handles only one level of the tree. This way, the recursion stacks create the entire tree level by level.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

To implement the merging of two binary trees as described in the problem statement, the solution uses a recursive depth-first search algorithm.

Here's a step-by-step breakdown of the algorithm:

The base case of the recursive function handles the case when either root1 or root2 is None. If one of them is None, it returns the other node, because there is nothing to merge.

if root1 is None:
    return root2
if root2 is None:
    return root1

If both nodes are not None, it creates a new TreeNode with the sum of both nodes' values. This will be the current node in the merged tree.
```
node = TreeNode(root1.val + root2.val)
```
To merge the left subtree of both trees, the function makes a recursive call with the left child of both root1 and root2 and assigns the return value to the left attribute of the new node.
```
node.left = self.mergeTrees(root1.left, root2.left)
```
Similarly, to merge the right subtree, another recursive call is made with the right child of both nodes. The return value is assigned to the right attribute of the new node.
```
node.right = self.mergeTrees(root1.right, root2.right)
```
After recursively merging both the left and right subtrees, the function returns the node, which now represents the root of the merged subtree for the current recursive call.
```
return node
```

This depth-first recursive approach systematically merges all nodes at corresponding positions in each level of both input trees. By continuously dividing the problem into smaller subproblems (merging the left and right children, respectively), the algorithm efficiently constructs the merged binary tree in a bottom-up manner, returning the merged root node as the result.

The space complexity of this algorithm is O(n), where n is the smaller of the heights of the two input trees because it is the maximum depth of the recursion stack. The time complexity is also O(n), where n in this case is the total number of nodes that will be present in the new merged tree, as each node from both trees is visited exactly once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider two simple binary trees to demonstrate the solution approach.

Tree 1:

   1
  / \
 3   2

Tree 2:

We want to merge Tree 1 and Tree 2 into a single tree. Following the step-by-step algorithm:

Start at the root of both trees. Since none of them are None, we create a new root node for the merged tree with the sum of the values of Tree 1's root (1) and Tree 2's root (2), giving us a root node with value 3.
Next, we merge the left children of both trees. Tree 1's left child has a value of 3 and Tree 2's left child has a value of 1. Neither is None, so we create a new node with the sum of their values (3 + 1 = 4) which becomes the left child of the merged tree's root.
Tree 2's left child also has a non-null right child with a value of 4. Tree 1 doesn't have a corresponding node here, so the merged tree's left child will inherit this right child directly.
Merging the right children of the root nodes from Tree 1 and Tree 2 results in a new node with the sum of their values (2 + 3 = 5), which becomes the right child of the merged tree's root.

The merged binary tree now looks like this:

Here is a step-by-step mapping of the decisions made to reach this merged tree:

Root node: Tree 1 has 1, Tree 2 has 2. The merged node has 3 (1 + 2).
Left child of the root node: Tree 1 has 3, Tree 2 has 1. The merged node has 4 (3 + 1).
Right child of root node: Tree 1 has 2, Tree 2 has 3. The merged node has 5 (2 + 3).
Right child of the left node: Tree 1 does not have a corresponding node, only Tree 2 has 4. The merged node has 4.

This walkthrough illustrates how the recursive algorithm systematically combines the node values of overlapping positions while retaining the node values of non-overlapping positions from the given trees to construct a merged tree.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, value=0, left=None, right=None):
4        self.value = value
5        self.left = left
6        self.right = right
7
8class Solution:
9    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
10        # If the first root is None, return the second root as the result of the merge.
11        if root1 is None:
12            return root2
13      
14        # If the second root is None, return the first root as the result of the merge.
15        if root2 is None:
16            return root1
17      
18        # If both roots are valid, create a new TreeNode with the sum of the values of root1 and root2.
19        merged_node = TreeNode(root1.value + root2.value)
20      
21        # Recursively merge the left children of both trees and assign to the left of the merged node.
22        merged_node.left = self.mergeTrees(root1.left, root2.left)
23      
24        # Recursively merge the right children of both trees and assign to the right of the merged node.
25        merged_node.right = self.mergeTrees(root1.right, root2.right)
26      
27        # Return the merged tree root node.
28        return merged_node
29

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int value; // Variable to store the value of the node
6    TreeNode left; // Reference to the left child node
7    TreeNode right; // Reference to the right child node
8
9    // Constructor to create a leaf node with a value
10    TreeNode(int value) { 
11        this.value = value; 
12    }
13
14    // Constructor to create a node with a value, left child, and right child
15    TreeNode(int value, TreeNode left, TreeNode right) { 
16        this.value = value;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22public class Solution {
23    /**
24     * Merges two binary trees by adding values of overlapping nodes together.
25     *
26     * @param root1 The root node of the first binary tree.
27     * @param root2 The root node of the second binary tree.
28     * @return A new binary tree with nodes merged from root1 and root2.
29     */
30    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
31        // If the first root is null, return the second root as the result of merge
32        if (root1 == null) {
33            return root2;
34        }
35      
36        // If the second root is null, return the first root as the result of merge
37        if (root2 == null) {
38            return root1;
39        }
40      
41        // Create a new TreeNode with a value equal to the sum of both node's values
42        TreeNode mergedNode = new TreeNode(root1.value + root2.value);
43      
44        // Recursively merge the left children of both roots and assign to the left of merged node
45        mergedNode.left = mergeTrees(root1.left, root2.left);
46      
47        // Recursively merge the right children of both roots and assign to the right of merged node
48        mergedNode.right = mergeTrees(root1.right, root2.right);
49      
50        // Return the merged tree node
51        return mergedNode;
52    }
53}
54

1#include <cstddef> //For NULL
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;             // The value of the node.
6    TreeNode *left;      // Pointer to the left child.
7    TreeNode *right;     // Pointer to the right child.
8  
9    // Constructor to create a new node with no children
10    TreeNode() : val(0), left(nullptr), right(nullptr) {}
11
12    // Constructor to create a new node with a specific value and no children
13    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14
15    // Constructor to create a new node with a value and two children
16    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
17};
18
19class Solution {
20public:
21    // Merges two binary trees into one binary tree.
22    // If nodes overlap, sum the values and create a new node with the sum.
23    // If nodes do not overlap, clone the non-null node.
24    TreeNode* mergeTrees(TreeNode* firstRoot, TreeNode* secondRoot) {
25        // If the first tree is empty, return the second tree (no merge required).
26        if (!firstRoot) return secondRoot;
27
28        // If the second tree is empty, return the first tree (no merge required).
29        if (!secondRoot) return firstRoot;
30
31        // Create a new node with the sum of the values of overlapping nodes.
32        TreeNode* mergedNode = new TreeNode(firstRoot->val + secondRoot->val);
33
34        // Recursively merge the left children.
35        mergedNode->left = mergeTrees(firstRoot->left, secondRoot->left);
36
37        // Recursively merge the right children.
38        mergedNode->right = mergeTrees(firstRoot->right, secondRoot->right);
39
40        // Return the root of the newly merged tree.
41        return mergedNode;
42    }
43};
44

1type TreeNodeOrNull = TreeNode | null;
2
3// Definition for a binary tree node.
4class TreeNode {
5  val: number;
6  left: TreeNodeOrNull;
7  right: TreeNodeOrNull;
8
9  constructor(val?: number, left?: TreeNodeOrNull = null, right?: TreeNodeOrNull = null) {
10    this.val = val !== undefined ? val : 0;
11    this.left = left;
12    this.right = right;
13  }
14}
15
16/**
17 * Merges two binary trees into a new binary tree.
18 * If two nodes overlap, the resulting node's value
19 * is a sum of the overlapping nodes' values.
20 * @param {TreeNodeOrNull} tree1 - The first binary tree.
21 * @param {TreeNodeOrNull} tree2 - The second binary tree.
22 * @returns {TreeNodeOrNull} - The merged binary tree.
23 */
24function mergeTrees(tree1: TreeNodeOrNull, tree2: TreeNodeOrNull): TreeNodeOrNull {
25  // If both trees are null, return null.
26  if (tree1 === null && tree2 === null) return null;
27  // If one tree is null, return the other tree.
28  if (tree1 === null) return tree2;
29  if (tree2 === null) return tree1;
30
31  // Merge the left and right subtrees recursively.
32  const mergedLeft = mergeTrees(tree1.left, tree2.left);
33  const mergedRight = mergeTrees(tree1.right, tree2.right);
34
35  // Create a new tree node with the sum of tree1 and tree2 node values,
36  // and the merged left and right subtrees as its children.
37  const mergedNode = new TreeNode(tree1.val + tree2.val, mergedLeft, mergedRight);
38
39  return mergedNode;
40}
41

Time and Space Complexity

The provided code defines a method for merging two binary trees. The function mergeTrees takes two binary trees (root nodes root1 and root2) as input and returns a new binary tree that represents the sum of both input trees.

Time Complexity:

The time complexity of the function is O(n), where n is the number of nodes present in the smaller of the two trees. This is because the function visits each node from both the trees exactly once (in the worst case, when both trees are of the same size). If the trees have a different number of nodes, the complexity is governed by the tree with fewer nodes since this is where the recursion will stop for each path.

Space Complexity:

The space complexity is also O(n), considering the worst-case scenario where the tree is completely unbalanced and resembles a linked list. In this case, n is again the number of nodes in the smaller tree. This is because the function will have a number of recursive calls on the stack proportional to the height of the tree, which, in the worst case, could be the number of nodes in the tree if it's completely unbalanced. For a balanced tree, the space complexity would be O(log(n)).

However, if we consider the space for the output tree, the space complexity would become O(m+n), where m and n are the number of nodes in root1 and root2, respectively, since a new tree of size at most m+n is created. But often, the space used to create the output is not considered when analyzing the algorithm itself, since that space is required for the output data structure.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know