Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 94
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given a binary tree of integers, find the maximum path sum between two nodes. The path must go through at least one node, and does not need to go through the root.

Pull request description:
Day94
Resolves #197. 

Patch:
diff --git a/README.md b/README.md
index 27f2276..38172cc 100644
--- a/README.md
+++ b/README.md
@@ -102,5 +102,6 @@ problems from
 * [Day 90](https://github.com/vaskoz/dailycodingproblem-go/issues/189)
 * [Day 91](https://github.com/vaskoz/dailycodingproblem-go/issues/192)
 * [Day 92](https://github.com/vaskoz/dailycodingproblem-go/issues/194)
+* [Day 94](https://github.com/vaskoz/dailycodingproblem-go/issues/197)
 * [Day 95](https://github.com/vaskoz/dailycodingproblem-go/issues/198)
 * [Day 96](https://github.com/vaskoz/dailycodingproblem-go/issues/200)
diff --git a/day94/problem.go b/day94/problem.go
new file mode 100644
index 0000000..b70eb90
--- /dev/null
+++ b/day94/problem.go
@@ -0,0 +1,41 @@
+package day94
+
+// BinaryTree is a binary tree with an integer value.
+type BinaryTree struct {
+	Value       int
+	Left, Right *BinaryTree
+}
+
+// MaxPathSum returns the maximum path sum in a given
+// binary tree.
+func MaxPathSum(tree *BinaryTree) int {
+	const MinInt = -int(^uint(0)>>1) - 1
+	result := MinInt
+	maxPathSum(tree, &result)
+	return result
+}
+
+func maxPathSum(node *BinaryTree, res *int) int {
+	if node == nil {
+		return 0
+	} else if node.Left == nil && node.Right == nil {
+		return node.Value
+	}
+	leftSum := maxPathSum(node.Left, res)
+	rightSum := maxPathSum(node.Right, res)
+	if node.Left != nil && node.Right != nil {
+		*res = max(*res, leftSum+rightSum+node.Value)
+		return max(leftSum, rightSum) + node.Value
+	}
+	if node.Left == nil {
+		return rightSum + node.Value
+	}
+	return leftSum + node.Value
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day94/problem_test.go b/day94/problem_test.go
new file mode 100644
index 0000000..de2caa1
--- /dev/null
+++ b/day94/problem_test.go
@@ -0,0 +1,35 @@
+package day94
+
+import "testing"
+
+var tree = &BinaryTree{
+	-15,
+	&BinaryTree{5,
+		&BinaryTree{-8,
+			&BinaryTree{2, nil, nil},
+			&BinaryTree{6, nil, nil}},
+		&BinaryTree{1, nil, nil}},
+	&BinaryTree{6,
+		&BinaryTree{3, nil, nil},
+		&BinaryTree{9, nil,
+			&BinaryTree{0,
+				&BinaryTree{4, nil, nil},
+				&BinaryTree{-1, &BinaryTree{10, nil, nil}, nil},
+			},
+		},
+	},
+}
+
+func TestMaxPathSum(t *testing.T) {
+	t.Parallel()
+	result := MaxPathSum(tree)
+	if result != 27 {
+		t.Errorf("Expected 27 got %v", result)
+	}
+}
+
+func BenchmarkMaxPathSum(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		MaxPathSum(tree)
+	}
+}