Merge Two Binary Trees

Problem

• You are given two binary trees root1 and root2. Return the merged tree.

Approach

• 1. Traverse both trees simultaneously and recursively
• 2. Trust the base cases
• 3. Essentially copy over everything from root2 to root1 and if they overlap then merge

Go Solution

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil && root2 == nil {
        return nil
    }
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }

    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Val = root1.Val + root2.Val
    root1.Right = mergeTrees(root1.Right, root2.Right)

    return root1
}