Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 89
Good morning! Here's your coding interview problem for today.

This problem was asked by LinkedIn.

Determine whether a tree is a valid binary search tree.

A binary search tree is a tree with two children, left and right, and satisfies the constraint that the key in the left child must be less than or equal to the root and the key in the right child must be greater than or equal to the root.

Pull request:
Day89
Resolves #187.

Patch:
diff --git a/README.md b/README.md
index fc4f1e4..56aaefc 100644
--- a/README.md
+++ b/README.md
@@ -98,3 +98,4 @@ problems from
 * [Day 86](https://github.com/vaskoz/dailycodingproblem-go/issues/181)
 * [Day 87](https://github.com/vaskoz/dailycodingproblem-go/issues/183)
 * [Day 88](https://github.com/vaskoz/dailycodingproblem-go/issues/185)
+* [Day 89](https://github.com/vaskoz/dailycodingproblem-go/issues/187)
diff --git a/day89/problem.go b/day89/problem.go
new file mode 100644
index 0000000..1d36eb5
--- /dev/null
+++ b/day89/problem.go
@@ -0,0 +1,24 @@
+package day89
+
+// BST represents a binary search tree.
+type BST struct {
+	Value       int
+	Left, Right *BST
+}
+
+// IsValidBST checks if the given tree conforms to the BST property.
+func IsValidBST(root *BST) bool {
+	const MaxInt = int(^uint(0) >> 1)
+	const MinInt = -MaxInt - 1
+	return isValidBST(root.Left, MinInt, root.Value) && isValidBST(root.Right, root.Value, MaxInt)
+}
+
+func isValidBST(root *BST, min, max int) bool {
+	if root == nil {
+		return true
+	}
+	if root.Value > min && root.Value <= max {
+		return isValidBST(root.Left, min, root.Value) && isValidBST(root.Right, root.Value, max)
+	}
+	return false
+}


Test patch:
diff --git a/day89/problem_test.go b/day89/problem_test.go
new file mode 100644
index 0000000..6cf01c8
--- /dev/null
+++ b/day89/problem_test.go
@@ -0,0 +1,29 @@
+package day89
+
+import "testing"
+
+var testcases = []struct {
+	root    *BST
+	isValid bool
+}{
+	{&BST{}, true},
+	{&BST{10, &BST{1, nil, nil}, &BST{20, nil, nil}}, true},
+	{&BST{10, &BST{20, nil, nil}, &BST{1, nil, nil}}, false},
+}
+
+func TestIsValidBST(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := IsValidBST(tc.root); result != tc.isValid {
+			t.Errorf("Expected %v got %v", tc.isValid, result)
+		}
+	}
+}
+
+func BenchmarkIsValidBST(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			IsValidBST(tc.root)
+		}
+	}
+}