Balanced Binary Tree Checker

A balanced binary tree is a crucial concept in computer science, particularly in the design of efficient data structures like search trees. A balanced tree ensures that operations like insertion, deletion, and searching have a predictable logarithmic time complexity, preventing worst-case scenarios where the tree degenerates into a linked list. This challenge will test your ability to traverse a binary tree and verify its balance property.

Problem Description

Given the root of a binary tree, determine if it is height-balanced.

A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one. In simpler terms, for every node in the tree, the height of its left subtree and the height of its right subtree must have an absolute difference of at most 1.

You should implement a function that takes the root of a binary tree as input and returns TRUE if the tree is height-balanced, and FALSE otherwise.

Key Requirements:

• The function must correctly identify whether a given binary tree adheres to the height-balanced property.
• The check needs to be performed recursively for every node in the tree.

Expected Behavior:

• If the input tree is empty (i.e., the root is NULL or None), it is considered balanced.
• For a non-empty tree, the absolute difference between the heights of the left and right subtrees of every node must be less than or equal to 1.

Edge Cases:

• An empty tree.
• A tree with only one node.
• A tree that is skewed (e.g., resembles a linked list).

Examples

Example 1:

Input:
    3
   / \
  9  20
    /  \
   15   7

Output: TRUE

Explanation:
The root node (3) has a left subtree of height 1 (node 9) and a right subtree of height 2 (nodes 20, 15, 7). The difference is 1, which is allowed.
Node 20 has a left subtree of height 1 (node 15) and a right subtree of height 1 (node 7). The difference is 0, which is allowed.
All other nodes are leaf nodes and trivially satisfy the condition.

Example 2:

Input:
    1
   / \
  2   2
 / \
3   3
/ \
4   4

Output: FALSE

Explanation:
The root node (1) has a left subtree of height 3 (nodes 2, 3, 4, 4) and a right subtree of height 1 (node 2). The difference is 2, which is greater than 1. Therefore, the tree is not balanced.

Example 3:

Input: NULL (or equivalent representation of an empty tree)

Output: TRUE

Explanation: An empty tree is considered balanced by definition.

Constraints

• The number of nodes in the tree will be between 0 and 5000.
• The value of each node will be between -10000 and 10000.
• Your solution should aim for an optimal time complexity, ideally O(N), where N is the number of nodes in the tree.

Notes

• You will need a way to represent a binary tree node, typically with a value, a left child pointer, and a right child pointer.
• Consider how you will calculate the height of a subtree.
• Think about how to efficiently combine the height calculation with the balance check to avoid redundant traversals.