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.
