Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 343
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given a binary search tree and a range `[a, b]` (inclusive), return the sum of the elements of the binary search tree within the range.

For example, given the following tree:
```
    5
   / \
  3   8
 / \ / \
2  4 6  10
```
and the range `[4, 9]`, return `23` `(5 + 4 + 6 + 8)`.

Pull request description:
Day343
Resolves #685.

Patch:
diff --git a/README.md b/README.md
index 75a020e..a473b19 100644
--- a/README.md
+++ b/README.md
@@ -333,6 +333,7 @@ problems from
 * [Day 339](https://github.com/vaskoz/dailycodingproblem-go/issues/676)
 * [Day 340](https://github.com/vaskoz/dailycodingproblem-go/issues/679)
 * [Day 342](https://github.com/vaskoz/dailycodingproblem-go/issues/682)
+* [Day 343](https://github.com/vaskoz/dailycodingproblem-go/issues/685)
 * [Day 345](https://github.com/vaskoz/dailycodingproblem-go/issues/687)
 * [Day 346](https://github.com/vaskoz/dailycodingproblem-go/issues/688)
 * [Day 347](https://github.com/vaskoz/dailycodingproblem-go/issues/689)
diff --git a/day343/problem.go b/day343/problem.go
new file mode 100644
index 0000000..3c1be59
--- /dev/null
+++ b/day343/problem.go
@@ -0,0 +1,22 @@
+package day343
+
+// BST is an integer binary search tree.
+type BST struct {
+	Val         int
+	Left, Right *BST
+}
+
+// SumBSTRange takes a BST root node and
+// two values indicating a range.
+// Runs in linear time recursively.
+func SumBSTRange(root *BST, a, b int) int {
+	if root == nil || a > b {
+		return 0
+	}
+	leftSum := SumBSTRange(root.Left, a, root.Val)
+	rightSum := SumBSTRange(root.Right, root.Val, b)
+	if root.Val >= a && root.Val <= b {
+		return root.Val + leftSum + rightSum
+	}
+	return leftSum + rightSum
+}


Test patch:
diff --git a/day343/problem_test.go b/day343/problem_test.go
new file mode 100644
index 0000000..94f68a1
--- /dev/null
+++ b/day343/problem_test.go
@@ -0,0 +1,62 @@
+package day343
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	root     *BST
+	a, b     int
+	expected int
+}{
+	{
+		&BST{
+			5,
+			&BST{
+				3,
+				&BST{2, nil, nil},
+				&BST{4, nil, nil},
+			},
+			&BST{
+				8,
+				&BST{6, nil, nil},
+				&BST{10, nil, nil},
+			},
+		},
+		4, 9,
+		23,
+	},
+	{
+		&BST{
+			5,
+			&BST{
+				3,
+				&BST{2, nil, nil},
+				&BST{4, nil, nil},
+			},
+			&BST{
+				8,
+				&BST{6, nil, nil},
+				&BST{10, nil, nil},
+			},
+		},
+		9, 4,
+		0,
+	},
+}
+
+func TestSumBSTRange(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if sum := SumBSTRange(tc.root, tc.a, tc.b); sum != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, sum)
+		}
+	}
+}
+
+func BenchmarkSumBSTRange(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SumBSTRange(tc.root, tc.a, tc.b)
+		}
+	}
+}