Check if Tree is Balanced 🎯

Welcome to the world of Data Structures and Algorithms! Today, we're going to learn about an important concept - Balanced Binary Trees. We'll also write a function to check if a given tree is balanced or not.

What is a Balanced Binary Tree? 📝

A binary tree is considered balanced if the difference between the heights of the left and right subtrees for every node is not more than 1. An unbalanced binary tree can lead to inefficient operations due to a skewed tree structure.

Why Balance Matters? 💡

Balanced binary trees ensure that operations like insertion, deletion, and searching are more efficient, especially in large datasets. It prevents the tree from becoming a linked list, where every node needs to be traversed to find a specific value.

Balanced Binary Tree Types 📝

There are two main types of balanced binary trees:

AVL Tree: A self-balancing binary search tree where the height difference between the left and right subtrees of each node is always between -1 and +1.
Red-Black Tree: A binary search tree where each node has an extra bit to store its color (red or black). It ensures that the height of the tree grows logarithmically, ensuring good performance.

Writing a Balanced Tree Checker Function 🎯

Let's write a simple function to check if a given binary tree is balanced or not. We'll create a helper function to calculate the height of the tree recursively.

python

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

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

def isBalanced(node):
    if node is None:
        return True
    lh = height(node.left)
    rh = height(node.right)

    if abs(lh - rh) > 1:
        return False

    return isBalanced(node.left) and isBalanced(node.right)

# Test case
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(isBalanced(root))  # Output: True

In this example, we create a simple binary tree and check if it's balanced using our isBalanced function.

That's it for today! You've learned about balanced binary trees, why they matter, and how to write a simple function to check if a given tree is balanced.

Stay tuned for more lessons on Data Structures and Algorithms! 💡