# [Leetcode][617. Merge Two Binary Trees] 4 Approaches: Recursion, Iteration, BFS and DFS

**By Long Luo**

This article is the solution of Problem 617. Merge Two Binary Trees.

Here are **4** approaches to solve this problem in Java.

# Recursion

## Method 1: New Tree

We can create a new **Tree**, each $\texttt{TreeNode}$ value is sum of two nodes.

1 | public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) { |

## 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 | public static TreeNode mergeTrees_rec(TreeNode root1, TreeNode root2) { |

## 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 $[node_{tree1}, 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 | public static TreeNode mergeTrees_bfs(TreeNode root1, TreeNode root2) { |

The BFS code is not neat, I have refactor it.

1 | public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { |

## 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 | public static TreeNode mergeTrees_dfs(TreeNode root1, TreeNode root2) { |

## 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. 😉😃💗