Balanced Binary Tree in Python

When it comes to organizing and accessing data, binary trees are immensely important in the domain of data structures. Out of the different types of binary trees, one type that especially stands out for its effectiveness in search, insert, and delete operations is the Balanced Binary Tree.

We will discuss the definition of a balanced binary tree, its significance, and the steps to implement one in Python.

What is a Balanced Binary Tree?

A Balanced Binary Tree is a binary tree where the height difference between the left and right subtrees of each node is restricted to a maximum of 1.

To put it another way, no subtree should outpace its sibling subtree in terms of depth by too great a margin. This balance is important in maintaining efficiency for searching, inserting, or deleting elements.

Get Chirag Chandel’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

A perfectly balanced binary tree optimizes most operations to around O(log n) in time complexity, in stark contrast to skewed trees that may suffer degradation to O(n).

Python Code to Check for a Balanced Binary Tree

Here’s a simple Python function to check whether a given binary tree is balanced:

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

def is_balanced(root):
    def check(node):
        if not node:
            return 0, True
        
        left_height, left_balanced = check(node.left)
        right_height, right_balanced = check(node.right)
        
        current_height = max(left_height, right_height) + 1
        is_bal = abs(left_height - right_height) <= 1
        
        return current_height, is_bal and left_balanced and right_balanced
    
    _, balanced = check(root)
    return balanced

Example Usage

# Creating a balanced tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Is tree balanced?", is_balanced(root))  # Output: True

Why Balanced Trees Matter

Operations on an unbalanced binary tree could lead to a deteriorated performance. This led to the creation of AVL Trees and Red-Black Trees which balance themselves after every operation.

Learn how to build, visualize, and optimize balanced binary trees in Python with interactive examples and practice problems.
Visit PrepInsta’s Balanced Binary Tree in Python Guide to become a DSA pro