Merge Two Binary Tree- LeetCode

Question

I solved this problem on LeetCode

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:
Input: 
 Tree 1 Tree 2 
 1 2 
 / \ / \ 
 3 2 1 3 
 / \ \ 
 5 4 7 
Output: 
Merged tree:
 3
 / \
 4 5
 / \ \ 
 5 4 7

Note: The merging process must start from the root nodes of both trees.

The code that I had written is.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * public int val;
 * public TreeNode left;
 * public TreeNode right;
 * public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
 public enum Direction
 {
 Left, Right, None
 }
 public TreeNode doMerge(TreeNode t1, TreeNode t2, Direction direction, TreeNode t3)
 {
 if(t1 == null && t2 == null)
 {
 return t3;
 }
 if(t1 == null || t2 == null)
 {
 TreeNode notNullTree = t1 == null ? t2 : t1;
 switch(direction)
 {
 case Direction.None:
 return notNullTree;
 case Direction.Left:
 t3.left = notNullTree;
 break;
 case Direction.Right:
 t3.right = notNullTree;
 break;
 }
 return t3;
 }
 var newNode = new TreeNode(t1.val + t2.val);
 switch (direction)
 {
 case Direction.None:
 t3 = newNode;
 break;
 case Direction.Left:
 t3.left = newNode;
 t3 = t3.left;
 break;
 case Direction.Right:
 t3.right = newNode;
 t3 = t3.right;
 break;
 }
 doMerge(t1.left, t2.left, Direction.Left, t3);
 doMerge(t1.right, t2.right, Direction.Right, t3);
 return t3;
 }
 public TreeNode MergeTrees(TreeNode t1, TreeNode t2)
 {
 return doMerge(t1, t2, Direction.None, null);
 }
}

The code has a lot of conditionals which could be refactored. Any suggestion on making the code a bit cleaner and concise would be helpful.

Answer 1

This is a very interesting problem!

Firstly, you have correctly identified the 3 possible states:

• both tree1 and tree2 are null
• tree1 or tree2 is null
• both tree1 and tree2 are not null

That being said, I would recommend a couple of things:

1. Break up the problem into 4 possible states (i.e., don't handle the case when tree1 or tree2 is null in one conditional statement.
2. if passing in the merged tree tree3 to doMerge in order to modify it in the method, you should utilize C#'s out parameter.
3. Why do you need the Direction enum? It seems to make the code harder to understand.

Here is my implementation of doMerge:

public TreeNode MergeTrees(TreeNode t1, TreeNode t2) 
{
 if (t1 == null && t2 == null) return null;
 if (t1 != null && t2 == null) return t1;
 if (t1 == null && t2 != null) return t2;
 TreeNode merged = new TreeNode(t1.val + t2.val);
 merged.left = MergeTrees(t1.left, t2.left);
 merged.right = MergeTrees(t1.right, t2.right);
 return merged;
}

Answer 2

Instead of iterative what you can do is make the recursive version as @ljeabmreson.

I successfully submitted this code on leetcode

public class Solution {
 public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
 return func(t1,t2);
 }
 public TreeNode func(TreeNode n1,TreeNode n2)
 {
 if(n1 == null && n2 == null)
 return null;
 else if(n1 != null && n2 != null)
 {
 TreeNode n = new TreeNode(n1.val + n2.val);
 n.left = func(n1.left,n2.left);
 n.right = func(n1.right,n2.right);
 return n;
 }
 else if(n1 != null && n2 == null)
 {
 TreeNode n = new TreeNode(n1.val);
 n.left = func(n1.left,null);
 n.right = func(n1.right,null);
 return n;
 }
 else
 {
 TreeNode n = new TreeNode(n2.val);
 n.left = func(null,n2.left);
 n.right = func(null,n2.right);
 return n;
 }
 }
}

But actually @ljeabmreson's version is a bit better as if only one of them is null, he is simply returning the other node and hence saving on time and space.

• thebenman: My version is not iterative. Its recursive as well.
• kumarmo2: i told that only. "make the recursive version as @ljeabmreson.". and i even mentioned that your code is a bit better than mine as well as it saves on space and time. :)