Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 116
Good morning! Here's your coding interview problem for today.

This problem was asked by Jane Street.

Generate a finite, but an arbitrarily large binary tree quickly in O(1).

That is, `generate()` should return a tree whose size is unbounded but finite.

Pull request description:
Day116
Resolves #242.

Patch:
diff --git a/README.md b/README.md
index af7c2fc..44e5348 100644
--- a/README.md
+++ b/README.md
@@ -124,3 +124,4 @@ problems from
 * [Day 112](https://github.com/vaskoz/dailycodingproblem-go/issues/235)
 * [Day 113](https://github.com/vaskoz/dailycodingproblem-go/issues/236)
 * [Day 114](https://github.com/vaskoz/dailycodingproblem-go/issues/237)
+* [Day 116](https://github.com/vaskoz/dailycodingproblem-go/issues/242)
diff --git a/day116/problem.go b/day116/problem.go
new file mode 100644
index 0000000..53c274b
--- /dev/null
+++ b/day116/problem.go
@@ -0,0 +1,42 @@
+package day116
+
+// UnboundBinaryTree is a tree that lazily grows.
+type UnboundBinaryTree interface {
+	Value() interface{}
+	Left() UnboundBinaryTree
+	Right() UnboundBinaryTree
+}
+
+type ubtTree struct {
+	value       interface{}
+	left, right *ubtTree
+}
+
+// Left returns the left child of this node.
+// Returns nil if the variable is set to nil.
+func (ubt *ubtTree) Left() UnboundBinaryTree {
+	if ubt.left == nil {
+		ubt.left = &ubtTree{}
+	}
+	return ubt.left
+}
+
+// Right returns the left child of this node.
+// Returns nil if the variable is set to nil.
+func (ubt *ubtTree) Right() UnboundBinaryTree {
+	if ubt.right == nil {
+		ubt.right = &ubtTree{}
+	}
+	return ubt.right
+}
+
+// Value returns the value stored at this node.
+// Returns nil if the variable is set to nil.
+func (ubt *ubtTree) Value() interface{} {
+	return ubt.value
+}
+
+// GenerateUnboundBinaryTree runs in O(1) time.
+func GenerateUnboundBinaryTree() UnboundBinaryTree {
+	return &ubtTree{}
+}


Test patch:
diff --git a/day116/problem_test.go b/day116/problem_test.go
new file mode 100644
index 0000000..db44cf1
--- /dev/null
+++ b/day116/problem_test.go
@@ -0,0 +1,29 @@
+package day116
+
+import "testing"
+
+func TestGenerateUnboundBinaryTree(t *testing.T) {
+	t.Parallel()
+	tree := GenerateUnboundBinaryTree()
+	for i := 0; i < 1000; i++ {
+		tree = tree.Left()
+		tree = tree.Right()
+	}
+	if tree.Value() != UnboundBinaryTree(nil) {
+		t.Errorf("The values are always nil of the interface type")
+	}
+	if tree.Left() == nil {
+		t.Errorf("The tree should be infinite. Left is nil")
+	}
+	if tree.Right() == nil {
+		t.Errorf("The tree should be infinite. Right is nil")
+	}
+}
+
+func BenchmarkGenerateUnboundBinaryTree(b *testing.B) {
+	tree := GenerateUnboundBinaryTree()
+	for i := 0; i < b.N; i++ {
+		tree = tree.Left()
+		tree = tree.Right()
+	}
+}