Python Program to Check if a Binary Tree is Height-Balanced

This program defines a function to check if a binary tree is height-balanced. A binary tree is height-balanced if, for every node, the height difference between its left and right subtrees is at most one. The algorithm uses a bottom-up approach, checking the balance from the leaves back up to the root, which allows it to be efficient by stopping early if imbalance is detected.

class TreeNode:
    """A node in a binary tree."""
    def __init__(self, x):
        """
        Initialize a tree node with a value.
        
        :param x: int, the integer value of the node
        """
        self.val = x
        self.left = None
        self.right = None

class Solution:
    """Solution to check if a binary tree is height-balanced."""
    
    def isBalanced(self, root):
        """
        Determine if the binary tree is height-balanced.
        
        :param root: TreeNode, the root of the binary tree
        :return: bool, True if the tree is balanced, False otherwise
        """
        def check_balance(node):
            """
            Check the balance of the tree and return the height if balanced.
            
            :param node: TreeNode, the current node
            :return: int, the height of the current subtree or -1 if it is not balanced
            """
            if not node:
                return 0
            
            left_height = check_balance(node.left)
            if left_height == -1: return -1  # Left subtree is not balanced
            
            right_height = check_balance(node.right)
            if right_height == -1: return -1  # Right subtree is not balanced
            
            if abs(left_height - right_height) > 1:
                return -1  # Current node is not balanced
            
            return max(left_height, right_height) + 1
        
        return check_balance(root) != -1

# Example Usage
if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(3)
    root.left.left.left = TreeNode(4)
    root.left.left.right = TreeNode(4)

    sol = Solution()
    balanced = sol.isBalanced(root)
    print("The tree is balanced:", balanced)

The program includes a TreeNode class for the structure of the tree nodes and a Solution class that houses the isBalanced function. The function uses a helper function check_balance that returns the height of the tree if it is balanced and -1 if not. This approach avoids unnecessary calculations by stopping as soon as an imbalance is detected.