By Long Luo

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.

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.

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}]$$.

1. We push the root nodes of both the trees onto the stack.
2. At every step, we remove a node pair from the top of the stack.
3. 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.
4. If $$root1.left != null && root2.left != null$$, we push the left child(pair) of both the trees onto the stack.
5. 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.
6. If, at any step, both the current nodes are null, we continue with popping the next nodes from the stack.

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.

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

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.

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