Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 296
Good morning! Here's your coding interview problem for today.

This problem was asked by Etsy.

Given a sorted array, convert it into a height-balanced binary search tree.

Pull request description:
Day296
Resolves #605.

Patch:
diff --git a/README.md b/README.md
index 70851d2..2534731 100644
--- a/README.md
+++ b/README.md
@@ -303,3 +303,4 @@ problems from
 * [Day 291](https://github.com/vaskoz/dailycodingproblem-go/issues/596)
 * [Day 294](https://github.com/vaskoz/dailycodingproblem-go/issues/600)
 * [Day 295](https://github.com/vaskoz/dailycodingproblem-go/issues/601)
+* [Day 296](https://github.com/vaskoz/dailycodingproblem-go/issues/605)
diff --git a/day296/problem.go b/day296/problem.go
new file mode 100644
index 0000000..f7ecf0f
--- /dev/null
+++ b/day296/problem.go
@@ -0,0 +1,19 @@
+package day296
+
+// BST is a binary search tree of integers.
+type BST struct {
+	Value       int
+	Left, Right *BST
+}
+
+// SortedSliceToBST constructs a BST from a sorted slice of ints.
+func SortedSliceToBST(sorted []int) *BST {
+	if len(sorted) == 0 {
+		return nil
+	}
+	mid := len(sorted) / 2
+	root := &BST{Value: sorted[mid]}
+	root.Left = SortedSliceToBST(sorted[:mid])
+	root.Right = SortedSliceToBST(sorted[mid+1:])
+	return root
+}


Test patch:
diff --git a/day296/problem_test.go b/day296/problem_test.go
new file mode 100644
index 0000000..29bf378
--- /dev/null
+++ b/day296/problem_test.go
@@ -0,0 +1,57 @@
+package day296
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	sorted   []int
+	expected *BST
+}{
+	{
+		[]int{1, 2, 3, 4, 5, 6, 7},
+		&BST{
+			4,
+			&BST{
+				2,
+				&BST{Value: 1},
+				&BST{Value: 3},
+			},
+			&BST{
+				6,
+				&BST{Value: 5},
+				&BST{Value: 7},
+			},
+		},
+	},
+}
+
+func TestSortedSliceToBST(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := SortedSliceToBST(tc.sorted); !equal(tc.expected, result) {
+			t.Errorf("BSTs don't match in TCID%d", tcid)
+		}
+	}
+}
+
+func BenchmarkSortedSliceToBST(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SortedSliceToBST(tc.sorted)
+		}
+	}
+}
+
+func equal(a, b *BST) 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.Value != b.Value:
+		return false
+	}
+	return equal(a.Left, b.Left) && equal(a.Right, b.Right)
+}