Merge two binary trees

Given two binary trees, return a merged tree

Merge rules:

• return sum if both nodes are exist
• if a right node is null return left node
• if a left node is null return right node

Example

 

/* Definition for TreeNode
public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}
*/

public sealed class Solution
{
    public TreeNode Merge(TreeNode one, TreeNode two)
    {
    }
}

Approach:

The easiest way is to use recursion and convert merge rules into a code. Could be following cases:

• Node one and node two are null
• Only node one is null
• Only node two is null
• Node one and node two are NOT null

and we have to do the same merging for left and right subtree

Code:

    public TreeNode Merge(TreeNode one, TreeNode two)
    {
        if (one == null && two == null)
        {
            return null;
        }

        if (one == null)
        {
            return two;
        }

        if (two == null)
        {
            return one;
        }

        one.Value += two.Value;
        one.Left = Merge(one.Left, two.Left);
        one.Right = Merge(one.Right, two.Right);
        return one;
    }