Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 133
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given a node in a binary tree, return the next bigger element, also known as the inorder successor.

For example, the inorder successor of 22 is 30.
```
   10
  /  \
 5    30
     /  \
   22    35
```
_You can assume each node has a parent pointer._

Pull request:
Day133
Resolves #275.

Patch:
diff --git a/README.md b/README.md
index 3b9f558..d64045c 100644
--- a/README.md
+++ b/README.md
@@ -140,3 +140,4 @@ problems from
 * [Day 130](https://github.com/vaskoz/dailycodingproblem-go/issues/265)
 * [Day 131](https://github.com/vaskoz/dailycodingproblem-go/issues/270)
 * [Day 132](https://github.com/vaskoz/dailycodingproblem-go/issues/272)
+* [Day 133](https://github.com/vaskoz/dailycodingproblem-go/issues/275)
diff --git a/day133/problem.go b/day133/problem.go
new file mode 100644
index 0000000..8f9f80c
--- /dev/null
+++ b/day133/problem.go
@@ -0,0 +1,21 @@
+package day133
+
+// BST is a binary search tree of integers.
+type BST struct {
+	Value               int
+	Left, Right, Parent *BST
+}
+
+// InorderSuccessor returns a pointer to the next bigger element.
+func InorderSuccessor(node *BST) *BST {
+	if node == nil {
+		return nil
+	} else if node.Right == nil {
+		return node.Parent
+	}
+	node = node.Right
+	for node.Left != nil {
+		node = node.Left
+	}
+	return node
+}


Test patch:
diff --git a/day133/problem_test.go b/day133/problem_test.go
new file mode 100644
index 0000000..f6cb4a6
--- /dev/null
+++ b/day133/problem_test.go
@@ -0,0 +1,50 @@
+package day133
+
+import "testing"
+
+var tree = createBST()
+
+var testcases = []struct {
+	givenNode, inorderSuccessor *BST
+}{
+	{nil, nil},
+	{tree.Right.Left, tree.Right},
+	{tree, tree.Right.Left},
+	{tree.Left, tree},
+	{tree.Right, tree.Right.Right},
+}
+
+func TestInorderSuccessor(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := InorderSuccessor(tc.givenNode); result != tc.inorderSuccessor {
+			t.Errorf("Nodes don't match for TCID%d", tcid)
+		}
+	}
+}
+
+func BenchmarkInorderSuccessor(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			InorderSuccessor(tc.givenNode)
+		}
+	}
+}
+
+func createBST() *BST {
+	bst := &BST{
+		Value:  10,
+		Parent: nil,
+		Left:   &BST{5, nil, nil, nil},
+		Right: &BST{
+			Value: 30,
+			Left:  &BST{22, nil, nil, nil},
+			Right: &BST{35, nil, nil, nil},
+		},
+	}
+	bst.Left.Parent = bst
+	bst.Right.Parent = bst
+	bst.Right.Left.Parent = bst.Right
+	bst.Right.Right.Parent = bst.Right
+	return bst
+}