Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 146
Good morning! Here's your coding interview problem for today.

This question was asked by BufferBox.

Given a binary tree where all nodes are either 0 or 1, prune the tree so that subtrees containing all 0s are removed.

For example, given the following tree:
```
   0
  / \
 1   0
    / \
   1   0
  / \
 0   0
```
should be pruned to:
```
   0
  / \
 1   0
    /
   1
```
We do not remove the tree at the root or its left child because it still has a 1 as a descendant.

Pull request description:
Day146
Resolves #303.

Patch:
diff --git a/README.md b/README.md
index 1eed3fe..bb128c6 100644
--- a/README.md
+++ b/README.md
@@ -154,4 +154,5 @@ problems from
 * [Day 141](https://github.com/vaskoz/dailycodingproblem-go/issues/294)
 * [Day 142](https://github.com/vaskoz/dailycodingproblem-go/issues/297)
 * [Day 143](https://github.com/vaskoz/dailycodingproblem-go/issues/299)
+* [Day 146](https://github.com/vaskoz/dailycodingproblem-go/issues/303)
 * [Day 147](https://github.com/vaskoz/dailycodingproblem-go/issues/304)
diff --git a/day146/problem.go b/day146/problem.go
new file mode 100644
index 0000000..2f4df1f
--- /dev/null
+++ b/day146/problem.go
@@ -0,0 +1,21 @@
+package day146
+
+// BinaryTree contains values of either zero (0) or one (1).
+type BinaryTree struct {
+	Value       int
+	Left, Right *BinaryTree
+}
+
+// PruneZeroSubtrees prunes all the subtrees containing only zeros.
+// NOTE: This mutates the input.
+func PruneZeroSubtrees(head *BinaryTree) *BinaryTree {
+	if head == nil {
+		return nil
+	}
+	head.Left = PruneZeroSubtrees(head.Left)
+	head.Right = PruneZeroSubtrees(head.Right)
+	if head.Value == 0 && head.Left == nil && head.Right == nil {
+		return nil
+	}
+	return head
+}


Test patch:
diff --git a/day146/problem_test.go b/day146/problem_test.go
new file mode 100644
index 0000000..3bfd21a
--- /dev/null
+++ b/day146/problem_test.go
@@ -0,0 +1,73 @@
+package day146
+
+import "testing"
+
+var testcases = []struct {
+	head, expected *BinaryTree
+}{
+	{&BinaryTree{
+		0,
+		&BinaryTree{
+			1,
+			nil,
+			nil,
+		},
+		&BinaryTree{
+			0,
+			&BinaryTree{
+				1,
+				&BinaryTree{
+					0,
+					nil,
+					nil,
+				},
+				&BinaryTree{
+					0,
+					nil,
+					nil,
+				},
+			},
+			&BinaryTree{
+				0,
+				nil,
+				nil,
+			},
+		},
+	},
+		&BinaryTree{
+			0,
+			&BinaryTree{1, nil, nil},
+			&BinaryTree{0,
+				&BinaryTree{1, nil, nil},
+				nil},
+		},
+	},
+}
+
+func TestPruneZeroSubtrees(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := PruneZeroSubtrees(tc.head); !treeEqual(result, tc.expected) {
+			t.Errorf("TCID%d didn't match", tcid)
+		}
+	}
+}
+
+func BenchmarkPruneZeroSubtrees(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PruneZeroSubtrees(tc.head)
+		}
+	}
+}
+
+func treeEqual(one, two *BinaryTree) bool {
+	if one == nil && two == nil {
+		return true
+	} else if one == nil && two != nil {
+		return false
+	} else if one != nil && two == nil {
+		return false
+	}
+	return treeEqual(one.Left, two.Left) && treeEqual(one.Right, two.Right)
+}