How to Determine if a Binary Tree is Height-Balanced using Python

Height Balanced Binary Tree

A binary tree data structure called as a "height-balanced binary tree," or "balanced binary tree," has left and right subtree heights of each node that are at most one unit apart. This is a crucial characteristic that ensures the efficiency of insertions and deletions as well as the balance of the tree.

The length of the longest path from root node toward a leaf node, measured in edges, is used to determine a binary tree's height. A height-balanced binary tree is significantly more effective than an imbalanced binary tree since the height of the tree is ensured to be logarithmic in the numbers of node of the tree.

AVL trees, red-black trees, and splay trees are a few of the strategies that may be employed to keep a binary tree balanced.
When a new node is added or an old node is destroyed, these techniques employ rotations to rebalance the tree.
Height-balanced binary trees offer quick search, insertion, and deletion operations in addition to their efficiency. They also make it simple to implement crucial algorithms like binary search, tree traversals, and data compression.
Overall, height-balanced binary trees are a practical and effective data structure that may be applied in a variety of settings, such as databases, search engines, and video games.

Examples of Height Balanced Binary Tree

How to Determine if a Binary Tree is Height-Balanced using Python

The root node in this instance is number 6. The heights of the right subtree (7, 8, 9, 10) and the left subtree (3, 2, 1) are both 2. The fact that there is just a one-height difference between the left and right subtrees indicates that the tree is height-balanced. The balancing of a tree can really alter over time as node are added or removed, despite the fact that the figure depicts a balanced tree. Algorithms like AVL trees, red-black trees, and splay trees are employed to ensure that the tree stays balance also after alterations in order to retain its equilibrium.

How to tell if a Binary Tree is Balanced in Height?

We can create a recursive method that measures the height of the tree and returns False if a left and right subtrees' heights differ by much more than one in order to assess whether a binary tree is height-balanced. Here is an illustration of a Python implementation:

Code

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def is_balanced(root):
    if root is None:
        return True

    left_height = height(root.left)
    right_height = height(root.right)

    if abs(left_height - right_height) <= 1 and is_balanced(root.left) and is_balanced(root.right):
        return True

    return False

def height(root):
    if root is None:
        return 0

    return max(height(root.left), height(root.right)) + 1

Explanation

The is balanced function in this example checks to see if the left and right subtrees' heights vary by more than one and returns False if they do. The height method returns the height limit of the left and right subtrees + 1 to determine the height of the tree. By supplying the tree's root node as the parameter, you may use the is balanced results to calculate whether a binary tree is height-balanced. The trees is height-balanced if the program runs True; else, it is not.

Program for Height Balanced Binary Tree

For an example of a height-balanced binary tree, see this Python programme:

Code

# Python program for checking the height balance of a binary tree

# Node of the binary tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
# is_balanced method to check the height
def is_balanced(root):
    if root is None:
        return True

    left_height = height(root.left)
    right_height = height(root.right)

    if abs(left_height - right_height) <= 1 and is_balanced(root.left) and is_balanced(root.right):
        return True

    return False

def height(root):
    if root is None:
        return 0

    return max(height(root.left), height(root.right)) + 1
# for testing the above functions
root = Node(6)
root.left = Node(3)
root.right = Node(7)
root.left.left = Node(2)
root.left.right = Node(5)
root.right.right = Node(8)
root.right.right.left = Node(9)
root.right.right.right = Node(10)
# if the condition becomes true
if is_balanced(root):
    print("The binary tree is height-balanced.")
else:
    print("The binary tree is not height-balanced.")

Output: