Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Binary Tree: Count Nodes and Find Deepest
Given the root to a binary tree, count the total number of nodes there are.

Given the root to a binary tree, return the deepest node.



Pull request description:
day 12 extra: count nodes and deepest node
Resolves #27 

Patch:
diff --git a/README.md b/README.md
index 3ee6ba8..f6e2e37 100644
--- a/README.md
+++ b/README.md
@@ -22,3 +22,4 @@ problems from
 * [Day 10](https://github.com/vaskoz/dailycodingproblem-go/issues/21)
 * [Day 11](https://github.com/vaskoz/dailycodingproblem-go/issues/23)
 * [Day 12](https://github.com/vaskoz/dailycodingproblem-go/issues/25)
+* [Day 12 Count and Deepest](https://github.com/vaskoz/dailycodingproblem-go/issues/27)
diff --git a/deepestBinaryTree/problem.go b/deepestBinaryTree/problem.go
new file mode 100644
index 0000000..b571d24
--- /dev/null
+++ b/deepestBinaryTree/problem.go
@@ -0,0 +1,35 @@
+package deepest
+
+// BinaryTree represents a tree with a left and right subtree.
+type BinaryTree struct {
+	// val         int // value doesn't matter here.
+	left, right *BinaryTree
+}
+
+// CountNodes tallies the total number of nodes in the binary tree.
+func CountNodes(root *BinaryTree) int {
+	if root == nil {
+		return 0
+	}
+	return CountNodes(root.left) + CountNodes(root.right) + 1
+}
+
+// Deepest returns the deepest node in the binary tree.
+func Deepest(root *BinaryTree) (*BinaryTree, int) {
+	if root != nil && root.left == nil && root.right == nil {
+		return root, 1
+	}
+	if root.left == nil {
+		n, count := Deepest(root.right)
+		return n, count + 1
+	} else if root.right == nil {
+		n, count := Deepest(root.left)
+		return n, count + 1
+	}
+	ln, lcount := Deepest(root.left)
+	rn, rcount := Deepest(root.right)
+	if lcount > rcount {
+		return ln, lcount + 1
+	}
+	return rn, rcount + 1
+}


Test patch:
diff --git a/deepestBinaryTree/problem_test.go b/deepestBinaryTree/problem_test.go
new file mode 100644
index 0000000..da65eba
--- /dev/null
+++ b/deepestBinaryTree/problem_test.go
@@ -0,0 +1,42 @@
+package deepest
+
+import "testing"
+
+// nodes = 5 depth = 3
+func buildTestTree() *BinaryTree {
+	return &BinaryTree{&BinaryTree{&BinaryTree{nil, nil},
+		&BinaryTree{&BinaryTree{nil, nil}, nil}},
+		&BinaryTree{nil, &BinaryTree{nil, nil}}}
+}
+
+func TestCountNodes(t *testing.T) {
+	t.Parallel()
+	root := buildTestTree()
+	if count := CountNodes(root); count != 7 {
+		t.Errorf("Expected 7 but got %v", count)
+	}
+}
+
+func BenchmarkCountNodes(b *testing.B) {
+	root := buildTestTree()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		CountNodes(root)
+	}
+}
+
+func TestDeepest(t *testing.T) {
+	t.Parallel()
+	root := buildTestTree()
+	if _, count := Deepest(root); count != 4 {
+		t.Errorf("Expected 4 but got %v", count)
+	}
+}
+
+func BenchmarkDeepest(b *testing.B) {
+	root := buildTestTree()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		Deepest(root)
+	}
+}