Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 247
Good morning! Here's your coding interview problem for today.

This problem was asked by PayPal.

Given a binary tree, determine whether or not it is height-balanced. A height-balanced binary tree can be defined as one in which the heights of the two subtrees of any node never differ by more than one.

Pull request:
Day247
Resolves #510.

Patch:
diff --git a/README.md b/README.md
index 137e627..660b03a 100644
--- a/README.md
+++ b/README.md
@@ -258,3 +258,4 @@ problems from
 * [Day 244](https://github.com/vaskoz/dailycodingproblem-go/issues/503)
 * [Day 245](https://github.com/vaskoz/dailycodingproblem-go/issues/506)
 * [Day 246](https://github.com/vaskoz/dailycodingproblem-go/issues/508)
+* [Day 247](https://github.com/vaskoz/dailycodingproblem-go/issues/510)
diff --git a/day247/problem.go b/day247/problem.go
new file mode 100644
index 0000000..82c1656
--- /dev/null
+++ b/day247/problem.go
@@ -0,0 +1,47 @@
+package day247
+
+// BinaryTree is a simple binary tree without a value.
+type BinaryTree struct {
+	// Value int // is unnecessary. We don't need any value.
+	Left, Right *BinaryTree
+}
+
+// IsHeightBalanced returns true if the tree is height balanced.
+// It returns false otherwise.
+// Runs in O(N) time.
+func IsHeightBalanced(root *BinaryTree) bool {
+	_, balanced := isHeightBalanced(root)
+	return balanced
+}
+
+func isHeightBalanced(n *BinaryTree) (int, bool) {
+	if n == nil {
+		return 0, true
+	}
+	leftHeight, leftBalance := isHeightBalanced(n.Left)
+	if !leftBalance {
+		return 0, false
+	}
+	rightHeight, rightBalance := isHeightBalanced(n.Right)
+	if !rightBalance {
+		return 0, false
+	}
+	if diff := abs(leftHeight - rightHeight); diff > 1 {
+		return 0, false
+	}
+	return max(leftHeight, rightHeight) + 1, true
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func abs(a int) int {
+	if a < 0 {
+		return -a
+	}
+	return a
+}


Test patch:
diff --git a/day247/problem_test.go b/day247/problem_test.go
new file mode 100644
index 0000000..f311c6c
--- /dev/null
+++ b/day247/problem_test.go
@@ -0,0 +1,74 @@
+package day247
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	root           *BinaryTree
+	heightBalanced bool
+}{
+	{
+		&BinaryTree{
+			&BinaryTree{nil, nil},
+			&BinaryTree{nil, nil},
+		},
+		true,
+	},
+	{
+		&BinaryTree{
+			nil,
+			&BinaryTree{nil, nil},
+		},
+		true,
+	},
+	{
+		&BinaryTree{
+			nil,
+			&BinaryTree{&BinaryTree{nil, nil}, nil},
+		},
+		false,
+	},
+	{
+		&BinaryTree{
+			nil,
+			&BinaryTree{
+				&BinaryTree{
+					nil,
+					&BinaryTree{nil, nil},
+				},
+				nil,
+			},
+		},
+		false,
+	},
+	{
+		&BinaryTree{
+			&BinaryTree{
+				nil,
+				&BinaryTree{
+					&BinaryTree{nil, nil},
+					nil,
+				},
+			},
+			nil,
+		},
+		false,
+	},
+}
+
+func TestIsHeightBalanced(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := IsHeightBalanced(tc.root); result != tc.heightBalanced {
+			t.Errorf("expected %v, got %v", tc.heightBalanced, result)
+		}
+	}
+}
+
+func BenchmarkIsHeightBalanced(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			IsHeightBalanced(tc.root)
+		}
+	}
+}