Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 135
Good morning! Here's your coding interview problem for today.

This question was asked by Apple.

Given a binary tree, find a minimum path sum from root to a leaf.

For example, the minimum path in this tree is `[10, 5, 1, -1]`, which has sum `15`.
```
  10
 /  \
5    5
 \     \
   2    1
       /
     -1
```

Pull request description:
Day135
Resolves #280.

Patch:
diff --git a/README.md b/README.md
index 565b564..451ceb1 100644
--- a/README.md
+++ b/README.md
@@ -143,3 +143,4 @@ problems from
 * [Day 132](https://github.com/vaskoz/dailycodingproblem-go/issues/272)
 * [Day 133](https://github.com/vaskoz/dailycodingproblem-go/issues/275)
 * [Day 134](https://github.com/vaskoz/dailycodingproblem-go/issues/278)
+* [Day 135](https://github.com/vaskoz/dailycodingproblem-go/issues/280)
diff --git a/day135/problem.go b/day135/problem.go
new file mode 100644
index 0000000..4764992
--- /dev/null
+++ b/day135/problem.go
@@ -0,0 +1,30 @@
+package day135
+
+// BinaryTree is a binary tree.
+type BinaryTree struct {
+	Value       int
+	Left, Right *BinaryTree
+}
+
+// MinPathSum returns the sum of the minimum sum path from root to leaf.
+func MinPathSum(head *BinaryTree) int {
+	if head.Left == nil && head.Right == nil {
+		return head.Value
+	}
+	if head.Left != nil && head.Right != nil {
+		left := head.Value + MinPathSum(head.Left)
+		right := head.Value + MinPathSum(head.Right)
+		return min(left, right)
+	} else if head.Left != nil {
+		return head.Value + MinPathSum(head.Left)
+	} else {
+		return head.Value + MinPathSum(head.Right)
+	}
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day135/problem_test.go b/day135/problem_test.go
new file mode 100644
index 0000000..122c484
--- /dev/null
+++ b/day135/problem_test.go
@@ -0,0 +1,34 @@
+package day135
+
+import "testing"
+
+var testcases = []struct {
+	tree   *BinaryTree
+	minSum int
+}{
+	{&BinaryTree{10,
+		&BinaryTree{5, nil, &BinaryTree{2, nil, nil}},
+		&BinaryTree{5, nil, &BinaryTree{1, &BinaryTree{-1, nil, nil}, nil}},
+	}, 15},
+	{&BinaryTree{10,
+		&BinaryTree{5, nil, &BinaryTree{1, &BinaryTree{-1, nil, nil}, nil}},
+		&BinaryTree{5, nil, &BinaryTree{2, nil, nil}},
+	}, 15},
+}
+
+func TestMinPathSum(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MinPathSum(tc.tree); result != tc.minSum {
+			t.Errorf("Expected %v got %v", tc.minSum, result)
+		}
+	}
+}
+
+func BenchmarkMinPathSum(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinPathSum(tc.tree)
+		}
+	}
+}