Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 36
Good morning! Here's your coding interview problem for today.

This problem was asked by Dropbox.

Given the root to a binary search tree, find the second largest node in the tree.

Pull request description:
Day36
Resolves #79 .

Patch:
diff --git a/README.md b/README.md
index bdb5283..f9dafaf 100644
--- a/README.md
+++ b/README.md
@@ -47,3 +47,4 @@ problems from
 * [Day 31](https://github.com/vaskoz/dailycodingproblem-go/issues/71)
 * [Day 33](https://github.com/vaskoz/dailycodingproblem-go/issues/73)
 * [Day 35](https://github.com/vaskoz/dailycodingproblem-go/issues/77)
+* [Day 36](https://github.com/vaskoz/dailycodingproblem-go/issues/79)
diff --git a/day36/problem.go b/day36/problem.go
new file mode 100644
index 0000000..cade081
--- /dev/null
+++ b/day36/problem.go
@@ -0,0 +1,29 @@
+package day36
+
+// BST represents a binary search tree.
+type BST struct {
+	val         int
+	left, right *BST
+}
+
+// SecondLargest takes the root of a binary search tree and returns the
+// pointer to the 2nd largest value.
+// Runs in O(height) and O(1) space.
+func SecondLargest(root *BST) int {
+	var prev, cur *BST
+	if root.right != nil {
+		prev = root
+		cur = root.right
+		for cur.right != nil {
+			cur = cur.right
+			prev = prev.right
+		}
+		cur = prev
+	} else {
+		cur = root.left
+		for cur.right != nil {
+			cur = cur.right
+		}
+	}
+	return cur.val
+}


Test patch:
diff --git a/day36/problem_test.go b/day36/problem_test.go
new file mode 100644
index 0000000..00d65d5
--- /dev/null
+++ b/day36/problem_test.go
@@ -0,0 +1,28 @@
+package day36
+
+import "testing"
+
+var testcases = []struct {
+	root     *BST
+	expected int
+}{
+	{&BST{10, nil, &BST{20, nil, &BST{30, nil, nil}}}, 20},
+	{&BST{10, &BST{5, nil, &BST{8, nil, nil}}, nil}, 8},
+}
+
+func TestSecondLargest(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := SecondLargest(tc.root); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkSecondLargest(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SecondLargest(tc.root)
+		}
+	}
+}