Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 204
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given a complete binary tree, count the number of nodes in faster than O(n) time. Recall that a complete binary tree has every level filled except the last, and the nodes in the last level are filled starting from the left.

Pull request description:
Day204
Resolves #421.

Patch:
diff --git a/README.md b/README.md
index 503807c..311e0fb 100644
--- a/README.md
+++ b/README.md
@@ -214,3 +214,4 @@ problems from
 * [Day 201](https://github.com/vaskoz/dailycodingproblem-go/issues/415)
 * [Day 202](https://github.com/vaskoz/dailycodingproblem-go/issues/417)
 * [Day 203](https://github.com/vaskoz/dailycodingproblem-go/issues/419)
+* [Day 204](https://github.com/vaskoz/dailycodingproblem-go/issues/421)
diff --git a/day204/problem.go b/day204/problem.go
new file mode 100644
index 0000000..c5c46f4
--- /dev/null
+++ b/day204/problem.go
@@ -0,0 +1,27 @@
+package day204
+
+// CompleteBinaryTree is a complete binary tree.
+type CompleteBinaryTree struct {
+	Value       interface{}
+	Left, Right *CompleteBinaryTree
+}
+
+// CountCompleteBinaryTree returns the number of nodes in a complete
+// binary tree is less than O(N) time.
+// Runs in O(height^2) time.
+func CountCompleteBinaryTree(tree *CompleteBinaryTree) int {
+	if tree == nil {
+		return 0
+	}
+	var leftHeight, rightHeight int
+	for left := tree; left != nil; left = left.Left {
+		leftHeight++
+	}
+	for right := tree; right != nil; right = right.Right {
+		rightHeight++
+	}
+	if leftHeight == rightHeight {
+		return (1 << uint(leftHeight)) - 1
+	}
+	return CountCompleteBinaryTree(tree.Left) + CountCompleteBinaryTree(tree.Right) + 1
+}


Test patch:
diff --git a/day204/problem_test.go b/day204/problem_test.go
new file mode 100644
index 0000000..8cbf56d
--- /dev/null
+++ b/day204/problem_test.go
@@ -0,0 +1,50 @@
+package day204
+
+import "testing"
+
+var testcases = []struct {
+	tree  *CompleteBinaryTree
+	count int
+}{
+	{&CompleteBinaryTree{
+		"a",
+		&CompleteBinaryTree{
+			"b",
+			&CompleteBinaryTree{
+				"d",
+				&CompleteBinaryTree{"h", nil, nil},
+				&CompleteBinaryTree{"i", nil, nil},
+			},
+			&CompleteBinaryTree{
+				"e",
+				&CompleteBinaryTree{"j", nil, nil},
+				&CompleteBinaryTree{"k", nil, nil},
+			}},
+		&CompleteBinaryTree{
+			"c",
+			&CompleteBinaryTree{
+				"f",
+				&CompleteBinaryTree{"l", nil, nil},
+				nil,
+			},
+			&CompleteBinaryTree{"g", nil, nil},
+		},
+	}, 12},
+}
+
+func TestCountCompleteBinaryTree(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if count := CountCompleteBinaryTree(tc.tree); count != tc.count {
+			t.Errorf("Expected %v, got %v", tc.count, count)
+		}
+	}
+}
+
+func BenchmarkCountCompleteBinaryTree(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CountCompleteBinaryTree(tc.tree)
+		}
+	}
+}