Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 115
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Pull request description:
Day115
Resolves #238.

Patch:
diff --git a/README.md b/README.md
index 44e5348..ba424c0 100644
--- a/README.md
+++ b/README.md
@@ -124,4 +124,5 @@ 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 115](https://github.com/vaskoz/dailycodingproblem-go/issues/238)
 * [Day 116](https://github.com/vaskoz/dailycodingproblem-go/issues/242)
diff --git a/day115/problem.go b/day115/problem.go
new file mode 100644
index 0000000..8f707b4
--- /dev/null
+++ b/day115/problem.go
@@ -0,0 +1,24 @@
+package day115
+
+// IntBinaryTree is a binary tree of integers.
+type IntBinaryTree struct {
+	Value       int
+	Left, Right *IntBinaryTree
+}
+
+// SameTreeSubstructure returns true if 't' exists somewhere inside of 's'.
+func SameTreeSubstructure(t, s *IntBinaryTree) bool {
+	if s == nil {
+		return false
+	}
+	return equalTrees(t, s) || SameTreeSubstructure(t, s.Left) || SameTreeSubstructure(t, s.Right)
+}
+
+func equalTrees(one, two *IntBinaryTree) bool {
+	if one == nil && two == nil {
+		return true
+	} else if (one == nil && two != nil) || (one != nil && two == nil) || (one.Value != two.Value) {
+		return false
+	}
+	return equalTrees(one.Left, two.Left) || equalTrees(one.Right, two.Right)
+}


Test patch:
diff --git a/day115/problem_test.go b/day115/problem_test.go
new file mode 100644
index 0000000..03c9c12
--- /dev/null
+++ b/day115/problem_test.go
@@ -0,0 +1,47 @@
+package day115
+
+import "testing"
+
+var testcases = []struct {
+	t, s     *IntBinaryTree
+	expected bool
+}{
+	{&IntBinaryTree{
+		10,
+		&IntBinaryTree{15, nil, nil},
+		&IntBinaryTree{20, nil, nil}},
+		&IntBinaryTree{15,
+			&IntBinaryTree{10,
+				&IntBinaryTree{15, nil, nil},
+				&IntBinaryTree{20, nil, nil}},
+			&IntBinaryTree{20, nil, nil}},
+		true},
+	{&IntBinaryTree{
+		10, nil, nil},
+		&IntBinaryTree{15,
+			&IntBinaryTree{25,
+				&IntBinaryTree{15, nil, nil},
+				&IntBinaryTree{20, nil, nil}},
+			&IntBinaryTree{20, nil, nil}},
+		false},
+	{&IntBinaryTree{10, nil, nil},
+		&IntBinaryTree{15, nil, nil},
+		false},
+}
+
+func TestSameTreeSubstructure(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := SameTreeSubstructure(tc.t, tc.s); result != tc.expected {
+			t.Errorf("TCID%d expected %v got %v", tcid, tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkSameTreeSubstructure(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SameTreeSubstructure(tc.t, tc.s)
+		}
+	}
+}