Python Program to Check if Binary Tree is Balanced

You can check if a binary tree is balanced by writing a function that returns the height of subtrees and ensures the height difference is never more than 1 using def is_balanced(root): with a helper function that returns -1 if unbalanced.

Examples

Inputroot = [1, 2, 3]

OutputTrue

Inputroot = [1, 2, null, 3]

OutputFalse

Inputroot = []

OutputTrue

How to Think About It

To check if a binary tree is balanced, think about the height of left and right subtrees for every node. If the difference in heights is more than 1 anywhere, the tree is not balanced. We can find this by checking heights from bottom to top and stopping early if imbalance is found.

Algorithm

1

Create a helper function that returns the height of a node or -1 if subtree is unbalanced

2

For each node, get the height of left and right children

3

If either child returns -1 or their height difference is more than 1, return -1

4

Otherwise, return the max height of children plus 1

5

Call the helper on the root and check if result is not -1 to decide if balanced

Code

python

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

def is_balanced(root):
    def height(node):
        if not node:
            return 0
        left_height = height(node.left)
        if left_height == -1:
            return -1
        right_height = height(node.right)
        if right_height == -1:
            return -1
        if abs(left_height - right_height) > 1:
            return -1
        return max(left_height, right_height) + 1
    return height(root) != -1

# Example usage:
root = TreeNode(1, TreeNode(2), TreeNode(3))
print(is_balanced(root))

Output

True

Dry Run

Let's trace the example tree with root = 1, left child = 2, right child = 3 through the code

1

Start at root node 1

Call height on node 1

2

Check left subtree of node 1

Call height on node 2, which has no children, returns 1

3

Check right subtree of node 1

Call height on node 3, which has no children, returns 1

4

Compare heights at node 1

Left height = 1, Right height = 1, difference = 0 <= 1, so return 2

5

Final result

height(root) = 2, not -1, so tree is balanced (True)

Node	Left Height	Right Height	Height Returned	Balanced?
2	0	0	1	Yes
3	0	0	1	Yes
1	1	1	2	Yes

Why This Works

Step 1: Calculate height bottom-up

The function calculates the height of each subtree starting from the leaves up to the root using recursion.

Step 2: Check balance at each node

At each node, it compares the heights of left and right subtrees using abs(left_height - right_height) > 1 to detect imbalance.

Step 3: Use -1 as a signal

If any subtree is unbalanced, the helper returns -1 immediately to stop further checks and propagate the failure.

Alternative Approaches

Top-down approach

python

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

def is_balanced(root):
    if not root:
        return True
    left_height = height(root.left)
    right_height = height(root.right)
    if abs(left_height - right_height) > 1:
        return False
    return is_balanced(root.left) and is_balanced(root.right)

# This method recalculates heights multiple times, less efficient.

Simple but inefficient because it recalculates heights repeatedly, leading to O(n^2) time.

Iterative using stack

python

def is_balanced(root):
    if not root:
        return True
    stack = [(root, 0)]
    heights = {}
    while stack:
        node, state = stack.pop()
        if node is None:
            continue
        if state == 0:
            stack.append((node, 1))
            stack.append((node.right, 0))
            stack.append((node.left, 0))
        else:
            left_height = heights.get(node.left, 0)
            right_height = heights.get(node.right, 0)
            if abs(left_height - right_height) > 1:
                return False
            heights[node] = max(left_height, right_height) + 1
    return True

# Uses explicit stack to avoid recursion, more complex but useful for large trees.

Avoids recursion stack overflow but is more complex to implement.

Complexity: O(n) time, O(h) space

Time Complexity

The algorithm visits each node once, so it runs in O(n) time where n is the number of nodes.

Space Complexity

The recursion stack can go as deep as the tree height h, so space is O(h).

Which Approach is Fastest?

The bottom-up approach with early stopping is fastest because it avoids repeated height calculations unlike the top-down method.

Approach	Time	Space	Best For
Bottom-up with early stop	O(n)	O(h)	Balanced check with best efficiency
Top-down recursive	O(n^2)	O(h)	Simple but slow for large trees
Iterative with stack	O(n)	O(h)	Avoid recursion, handle large trees