How to check if tree is balanced

Data-structures-theoryHow-ToBeginner · 4 min read

How to Check if a Tree is Balanced: Simple Explanation and Code

To check if a tree is balanced, verify that for every node, the height difference between its left and right subtrees is at most 1. Use a recursive function that returns the height of subtrees and checks balance at each node using height and balance conditions.

📐

Syntax

The main idea is to create a recursive function that returns the height of a subtree if it is balanced, or -1 if it is not. The function checks the left and right subtree heights, then compares their difference.

checkBalance(node): Returns height if balanced, else -1.
height: The number of edges on the longest path from the node to a leaf.
Balance condition: abs(leftHeight - rightHeight) <= 1.

python

def checkBalance(node):
    if node is None:
        return 0
    leftHeight = checkBalance(node.left)
    if leftHeight == -1:
        return -1
    rightHeight = checkBalance(node.right)
    if rightHeight == -1:
        return -1
    if abs(leftHeight - rightHeight) > 1:
        return -1
    return max(leftHeight, rightHeight) + 1

💻

Example

This example demonstrates how to check if a binary tree is balanced by using the recursive checkBalance function. It returns True if balanced, False otherwise.

python

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

def checkBalance(node):
    if node is None:
        return 0
    leftHeight = checkBalance(node.left)
    if leftHeight == -1:
        return -1
    rightHeight = checkBalance(node.right)
    if rightHeight == -1:
        return -1
    if abs(leftHeight - rightHeight) > 1:
        return -1
    return max(leftHeight, rightHeight) + 1

def isBalanced(root):
    return checkBalance(root) != -1

# Example tree:
#       1
#      / \
#     2   3
#    / 
#   4

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

print(isBalanced(root))  # Output: True

# Adding an extra node to make it unbalanced
root.left.left.left = Node(5)
print(isBalanced(root))  # Output: False

Output

True False

⚠️

Common Pitfalls

Common mistakes when checking if a tree is balanced include:

Calculating height separately for each node without caching, causing inefficient repeated work.
Checking balance only at the root, missing unbalanced subtrees deeper in the tree.
Using a separate function to calculate height and another to check balance, leading to O(n²) time complexity.

The correct approach combines height calculation and balance check in one recursive function to achieve O(n) time.

python

def wrongCheckBalance(node):
    if node is None:
        return True
    leftHeight = height(node.left)
    rightHeight = height(node.right)
    if abs(leftHeight - rightHeight) > 1:
        return False
    return wrongCheckBalance(node.left) and wrongCheckBalance(node.right)

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

# This approach recalculates height many times, causing inefficiency.

📊

Quick Reference

Use a single recursive function to check balance and compute height.
Return -1 immediately if any subtree is unbalanced.
Balance condition: height difference ≤ 1 at every node.
Time complexity: O(n), where n is number of nodes.

✅

Key Takeaways

Check balance by comparing left and right subtree heights at every node.

Use a single recursive function returning height or -1 for efficiency.

Return -1 immediately when imbalance is detected to avoid extra work.

Avoid separate height and balance checks to prevent O(n²) time complexity.

A balanced tree has height differences of at most 1 at all nodes.