[LeetCode][617. Merge Two Binary Trees] 4 Approaches: Recursion, Iteration, BFS and DFS
By Long Luo
This article is the solution 4 Approaches: Recursion, Iteration, BFS and DFS of Problem 617. Merge Two Binary Trees.
Here are 4 approaches to solve this problem in Java: Recursion, Iteration, BFS and DFS.
Recursion
Method 1: New Tree
We can create a new Tree, each \(\texttt{TreeNode}\) value is sum of two nodes.1
2
3
4
5
6
7
8
9
10
11
12public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
TreeNode merged = new TreeNode(root1.val + root2.val);
merged.left = mergeTrees(root1.left, root2.left);
merged.right = mergeTrees(root1.right, root2.right);
return merged;
}
Analysis
- Time Complexity: \(O(min(m, n))\)
- Space Complexity: \(O(min(m, n))\)
Method 2
Traverse both the given trees in a PreOrder style.
At every step, check if the current node exists for both the trees. If one of these children happens to be null, we return the child of the other tree to be added as a child subtree to the calling parent node in the first tree.
We can add the values in the current nodes of both the trees and update the value in the current node of the first tree to reflect this sum obtained.
Then we call the \(\texttt{mergeTrees()}\) with the left children and then with the right children of the current nodes of the two trees.
At the end, the first tree will represent the required resultant merged binary tree.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public static TreeNode mergeTrees_rec(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
if (root1 != null) {
root1.val += root2.val;
root1.left = mergeTrees_rec(root1.left, root2.left);
root1.right = mergeTrees_rec(root1.right, root2.right);
}
return root1;
}
Analysis
- Time Complexity: \(O(min(m, n))\)
- Space Complexity: \(O(min(m, n))\)
Iteration
We can also traverse the two trees by make use of a stack to do so.
Each entry in the Stack strores data in the form \([\textit{node}_{tree1}, \textit{node}_{tree2}]\).
- We push the root nodes of both the trees onto the stack.
- At every step, we remove a node pair from the top of the stack.
- For every node pair removed, we add the values corresponding to the two nodes and update the value of the corresponding node in the first tree.
- If \(root1.left != null && root2.left != null\), we push the left child(pair) of both the trees onto the stack.
- If \(root1.left == null\), we append the left child(subtree) of the second tree to the current node of the first tree. We do the same for the right child pair as well.
- If, at any step, both the current nodes are null, we continue with popping the next nodes from the stack.
1 | public TreeNode mergeTrees_iter(TreeNode root1, TreeNode root2) { |
Analysis
- Time Complexity: \(O(min(m, n))\)
- Space Complexity: \(O(min(m, n))\)
BFS
BFS is like the Iteration method, it create a new Tree.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49public static TreeNode mergeTrees_bfs(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
} else if (root2 == null) {
return root1;
}
TreeNode merged = new TreeNode(root1.val + root2.val);
Queue<TreeNode> queue = new LinkedList<>();
Queue<TreeNode> queue1 = new LinkedList<>();
Queue<TreeNode> queue2 = new LinkedList<>();
queue.offer(merged);
queue1.offer(root1);
queue2.offer(root2);
while (!queue1.isEmpty() && !queue2.isEmpty()) {
TreeNode node = queue.poll();
TreeNode node1 = queue1.poll();
TreeNode node2 = queue2.poll();
if (node1.left != null || node2.left != null) {
if (node1.left != null && node2.left != null) {
TreeNode leftNode = new TreeNode(node1.left.val + node2.left.val);
node.left = leftNode;
queue.offer(leftNode);
queue1.offer(node1.left);
queue2.offer(node2.left);
} else if (node1.left != null) {
node.left = node1.left;
} else if (node2.left != null) {
node.left = node2.left;
}
}
if (node1.right != null || node2.right != null) {
if (node1.right != null && node2.right != null) {
TreeNode rightNode = new TreeNode(node1.right.val + node2.right.val);
node.right = rightNode;
queue.offer(rightNode);
queue1.offer(node1.right);
queue2.offer(node2.right);
} else if (node1.right != null) {
node.right = node1.right;
} else if (node2.right != null) {
node.right = node2.right;
}
}
}
return merged;
}
The BFS code is not neat, I have refactor it.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
} else if (root2 == null) {
return root1;
}
Queue<TreeNode[]> queue = new LinkedList<>();
queue.offer(new TreeNode[]{root1, root2});
while (!queue.isEmpty()) {
TreeNode[] node = queue.poll();
node[0].val += node[1].val;
if (node[0].left != null || node[1].left != null) {
if (node[0].left != null && node[1].left != null) {
queue.offer(new TreeNode[]{node[0].left, node[1].left});
} else if (node[0].left == null) {
node[0].left = node[1].left;
}
}
if (node[0].right != null || node[1].right != null) {
if (node[0].right != null && node[1].right != null) {
queue.offer(new TreeNode[]{node[0].right, node[1].right});
} else if (node[0].right == null) {
node[0].right = node[1].right;
}
}
}
return root1;
}
Analysis
- Time Complexity: \(O(min(m, n))\)
- Space Complexity: \(O(min(m, n))\)
DFS
DFS is the same as the recursion method, just a little bit difference.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public static TreeNode mergeTrees_dfs(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
dfs(root1, root2);
return root1;
}
public static void dfs(TreeNode root1, TreeNode root2) {
if (root1 != null && root2 != null) {
if (root1 != root2) {
root1.val += root2.val;
}
if (root1.left == null) {
root1.left = root2.left;
}
if (root1.right == null) {
root1.right = root2.right;
}
dfs(root1.left, root2.left);
dfs(root1.right, root2.right);
}
}
Analysis
- Time Complexity: \(O(min(m, n))\)
- Space Complexity: \(O(min(m, n))\)
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗