Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 327
Good morning! Here's your coding interview problem for today.

This problem was asked by Salesforce.

Write a program to merge two binary trees. Each node in the new tree should hold a value equal to the sum of the values of the corresponding nodes of the input trees.

If only one input tree has a node in a given position, the corresponding node in the new tree should match that input node.

Pull request:
Day327
Resolves #662.

Patch:
diff --git a/day327/problem.go b/day327/problem.go
new file mode 100644
index 0000000..2989aea
--- /dev/null
+++ b/day327/problem.go
@@ -0,0 +1,32 @@
+package day327
+
+// BinaryTree is an integer binary tree.
+type BinaryTree struct {
+	Val         int
+	Left, Right *BinaryTree
+}
+
+// MergeBinaryTrees returns a new binary tree that is the "merge"
+// of two other binary trees.
+// Merge is defined as the sum of equivalently placed nodes.
+// Runs in O(N) time.
+func MergeBinaryTrees(one, two *BinaryTree) *BinaryTree {
+	switch {
+	case one == nil && two == nil:
+		return nil
+	case one == nil:
+		return &BinaryTree{two.Val,
+			MergeBinaryTrees(nil, two.Left),
+			MergeBinaryTrees(nil, two.Right),
+		}
+	case two == nil:
+		return &BinaryTree{one.Val,
+			MergeBinaryTrees(one.Left, nil),
+			MergeBinaryTrees(one.Right, nil),
+		}
+	}
+	return &BinaryTree{one.Val + two.Val,
+		MergeBinaryTrees(one.Left, two.Left),
+		MergeBinaryTrees(one.Right, two.Right),
+	}
+}


Test patch:
diff --git a/day327/problem_test.go b/day327/problem_test.go
new file mode 100644
index 0000000..965697b
--- /dev/null
+++ b/day327/problem_test.go
@@ -0,0 +1,111 @@
+package day327
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	one, two, merged *BinaryTree
+}{
+	{
+		&BinaryTree{
+			5,
+			&BinaryTree{
+				Val: 9,
+			},
+			&BinaryTree{
+				Val: 11,
+			},
+		},
+		&BinaryTree{
+			6,
+			&BinaryTree{
+				Val: 10,
+			},
+			&BinaryTree{
+				Val: 21,
+			},
+		},
+		&BinaryTree{
+			11,
+			&BinaryTree{
+				Val: 19,
+			},
+			&BinaryTree{
+				Val: 32,
+			},
+		},
+	},
+	{
+		&BinaryTree{
+			5,
+			&BinaryTree{
+				Val: 9,
+			},
+			nil,
+		},
+		&BinaryTree{
+			6,
+			nil,
+			&BinaryTree{
+				Val: 21,
+			},
+		},
+		&BinaryTree{
+			11,
+			&BinaryTree{
+				Val: 9,
+			},
+			&BinaryTree{
+				Val: 21,
+			},
+		},
+	},
+	{
+		&BinaryTree{
+			5,
+			&BinaryTree{
+				Val: 9,
+			},
+			nil,
+		},
+		nil,
+		&BinaryTree{
+			5,
+			&BinaryTree{
+				Val: 9,
+			},
+			nil,
+		},
+	},
+}
+
+func TestMergeBinaryTree(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := MergeBinaryTrees(tc.one, tc.two); !equal(result, tc.merged) {
+			t.Errorf("Trees in TCID%d don't match", tcid)
+		}
+	}
+}
+
+func BenchmarkMergeBinaryTree(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MergeBinaryTrees(tc.one, tc.two)
+		}
+	}
+}
+
+func equal(a, b *BinaryTree) bool {
+	switch {
+	case a == nil && b != nil:
+		return false
+	case a != nil && b == nil:
+		return false
+	case a == nil && b == nil:
+		return true
+	case a.Val != b.Val:
+		return false
+	}
+	return equal(a.Left, b.Left) && equal(a.Right, b.Right)
+}