Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 8
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

A unival tree (which stands for "universal value") is a tree where all nodes under it have the same value.

Given the root to a binary tree, count the number of unival subtrees.

For example, the following tree has 5 unival subtrees:
```
   0
  / \
 1   0
    / \
   1   0
  / \
 1   1
```

Pull request:
Day8
Closes #17.

Patch:
diff --git a/README.md b/README.md
index 200854f..116080e 100644
--- a/README.md
+++ b/README.md
@@ -17,3 +17,4 @@ problems from
 * [Day 5 merge k sorted lists](https://github.com/vaskoz/dailycodingproblem-go/issues/11)
 * [Day 6](https://github.com/vaskoz/dailycodingproblem-go/issues/13)
 * [Day 7](https://github.com/vaskoz/dailycodingproblem-go/issues/15)
+* [Day 8](https://github.com/vaskoz/dailycodingproblem-go/issues/17)
diff --git a/day8/problem.go b/day8/problem.go
new file mode 100644
index 0000000..d8129c2
--- /dev/null
+++ b/day8/problem.go
@@ -0,0 +1,32 @@
+package day8
+
+// BinaryTree represents a binary unival tree.
+type BinaryTree struct {
+	value       int
+	left, right *BinaryTree
+}
+
+// CountUnivalSubtrees counts the number of unival subtrees.
+func CountUnivalSubtrees(root *BinaryTree) int {
+	count, _ := countUnivalSubtrees(root)
+	return count
+}
+
+func countUnivalSubtrees(root *BinaryTree) (int, bool) {
+	if root == nil {
+		return 0, true
+	}
+	left, leftUnival := countUnivalSubtrees(root.left)
+	right, rightUnival := countUnivalSubtrees(root.right)
+	total := left + right
+	if leftUnival && rightUnival {
+		if root.left != nil && root.value != root.left.value {
+			return total, false
+		}
+		if root.right != nil && root.value != root.right.value {
+			return total, false
+		}
+		return total + 1, true
+	}
+	return total, false
+}


Test patch:
diff --git a/day8/problem_test.go b/day8/problem_test.go
new file mode 100644
index 0000000..2974769
--- /dev/null
+++ b/day8/problem_test.go
@@ -0,0 +1,47 @@
+package day8
+
+import "testing"
+
+func TestCountUnivalSubtrees(t *testing.T) {
+	root := &BinaryTree{value: 0,
+		left: &BinaryTree{value: 1},
+		right: &BinaryTree{value: 0,
+			left: &BinaryTree{value: 1,
+				left:  &BinaryTree{value: 1},
+				right: &BinaryTree{value: 1}},
+			right: &BinaryTree{value: 0}}}
+	if count := CountUnivalSubtrees(root); count != 5 {
+		t.Errorf("expected %v, but got %v", 5, count)
+	}
+	root = &BinaryTree{value: 0,
+		left: &BinaryTree{value: 1},
+		right: &BinaryTree{value: 0,
+			left: &BinaryTree{value: 0},
+			right: &BinaryTree{value: 1,
+				left:  &BinaryTree{value: 1},
+				right: &BinaryTree{value: 1}}}}
+	if count := CountUnivalSubtrees(root); count != 5 {
+		t.Errorf("expected %v, but got %v", 5, count)
+	}
+}
+
+func BenchmarkCountUnivalSubtrees(b *testing.B) {
+	root1 := &BinaryTree{value: 0,
+		left: &BinaryTree{value: 1},
+		right: &BinaryTree{value: 0,
+			left: &BinaryTree{value: 1,
+				left:  &BinaryTree{value: 1},
+				right: &BinaryTree{value: 1}},
+			right: &BinaryTree{value: 0}}}
+	root2 := &BinaryTree{value: 0,
+		left: &BinaryTree{value: 1},
+		right: &BinaryTree{value: 0,
+			left: &BinaryTree{value: 0},
+			right: &BinaryTree{value: 1,
+				left:  &BinaryTree{value: 1},
+				right: &BinaryTree{value: 1}}}}
+	for i := 0; i < b.N; i++ {
+		CountUnivalSubtrees(root1)
+		CountUnivalSubtrees(root2)
+	}
+}