Solving Balanced Binary Tree in Python: Step-by-Step Guide

Introduction to Balanced Binary Trees

A balanced binary tree is a binary tree data structure in which the depth (or height) of the left and right subtrees of every node differ by no more than one. This property is crucial because it ensures that operations like insertion, deletion, and search remain efficient, typically running in O(log n) time complexity rather than degrading to O(n) in the worst case of a skewed tree.

In coding interviews and algorithm design, the "Balanced Binary Tree" problem—often found on platforms like LeetCode (Problem 110)—asks you to determine whether a given binary tree is height-balanced. This tutorial walks you through solving this problem in Python, from a naive approach to an optimized solution.

What Is a Balanced Binary Tree?

Formally, a binary tree is considered balanced if, for every node in the tree, the following conditions hold:

The heights of the left and right subtrees differ by at most one.
The left subtree is itself balanced.
The right subtree is itself balanced.

This recursive definition means you cannot simply check the root node; you must verify the balance condition at every single node. A tree that appears balanced at the root could still be unbalanced deeper within one of its subtrees.

Examples

Consider the following balanced tree:

At node 1, the left subtree has height 2 and the right subtree has height 1—a difference of 1, which is acceptable. All other nodes also satisfy the condition, so the tree is balanced.

Now consider this unbalanced tree:

At node 1, the left subtree has height 0 (empty) while the right subtree has height 3. The difference is 3, which exceeds 1, making the tree unbalanced.

Why Balanced Binary Trees Matter

Balance is not just an academic concern—it directly impacts performance. When a binary tree becomes skewed (essentially behaving like a linked list), operations that should be logarithmic become linear. This is why self-balancing trees like AVL trees and Red-Black trees were invented: they automatically maintain balance during insertions and deletions.

Understanding how to check for balance also teaches fundamental concepts:

Recursive tree traversal
Computing subtree heights efficiently
Recognizing overlapping subproblems (a hallmark of dynamic programming)
Early termination in recursive algorithms

Defining the Tree Node

Before writing any solution, we need a class to represent tree nodes. In Python, this is typically defined as follows:

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

Each node stores a value and references to its left and right children. We will use this class throughout the tutorial.

Approach 1: Top-Down Recursion (Naive)

The most intuitive approach is to directly translate the definition into code. For each node, compute the height of the left and right subtrees, check if their difference is at most one, and then recursively verify that both subtrees are balanced.

Implementation

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


class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if root is None:
            return True

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

        if abs(left_height - right_height) > 1:
            return False

        return self.isBalanced(root.left) and self.isBalanced(root.right)

    def height(self, node: TreeNode) -> int:
        if node is None:
            return 0
        return 1 + max(self.height(node.left), self.height(node.right))

Complexity Analysis

This approach works correctly but is inefficient. The height function is called repeatedly on the same nodes. For a node at depth d, its height is computed once for each ancestor above it. This leads to O(n²) time complexity in the worst case (a skewed tree). The space complexity is O(n) due to the recursion stack.

Approach 2: Bottom-Up Recursion (Optimized)

The inefficiency in the naive approach comes from recomputing heights. A better strategy is to compute the height and check balance in a single pass. We traverse the tree bottom-up: at each node, we first recursively check its children. If a subtree is unbalanced, we propagate a signal upward immediately, avoiding further unnecessary computation.

Implementation

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


class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def check(node: TreeNode) -> int:
            # Returns the height of the node if balanced,
            # or -1 if the subtree is unbalanced.
            if node is None:
                return 0

            left = check(node.left)
            if left == -1:
                return -1

            right = check(node.right)
            if right == -1:
                return -1

            if abs(left - right) > 1:
                return -1

            return 1 + max(left, right)

        return check(root) != -1

How It Works

The inner check function returns a sentinel value of -1 whenever it detects an imbalance. This serves two purposes: it signals that the tree is unbalanced, and it triggers early termination. Once any subtree returns -1, the recursion unwinds quickly without computing further heights.

If a subtree is balanced, check returns its actual height, which the parent node uses to compute its own height and balance status.

Complexity Analysis

Each node is visited exactly once, so the time complexity is O(n), where n is the number of nodes. The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In a balanced tree, this is O(log n); in the worst case (skewed tree), it is O(n).

Testing the Solution

Let us build a few test cases to verify our implementation:

# Helper function to build a tree from a list (level-order)
from collections import deque

def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root


# Test cases
solution = Solution()

# Test 1: Balanced tree
#       3
#      / \
#     9  20
#       /  \
#      15   7
tree1 = build_tree([3, 9, 20, None, None, 15, 7])
print(solution.isBalanced(tree1))  # Output: True

# Test 2: Unbalanced tree
#       1
#      / \
#     2   2
#    / \
#   3   3
#  / \
# 4   4
tree2 = build_tree([1, 2, 2, 3, 3, None, None, 4, 4])
print(solution.isBalanced(tree2))  # Output: False

# Test 3: Empty tree
tree3 = build_tree([])
print(solution.isBalanced(tree3))  # Output: True

# Test 4: Single node
tree4 = build_tree([1])
print(solution.isBalanced(tree4))  # Output: True

# Test 5: Right-skewed tree
tree5 = build_tree([1, None, 2, None, 3])
print(solution.isBalanced(tree5))  # Output: False

All test cases should produce the expected outputs, confirming that the algorithm handles balanced trees, unbalanced trees, empty trees, single nodes, and skewed trees correctly.

Approach 3: Iterative Post-Order Traversal

For environments where recursion depth is a concern (very deep trees may hit Python's recursion limit), an iterative solution using post-order traversal is a robust alternative. We simulate the recursion using an explicit stack and track visited status for each node.

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if root is None:
            return True

        stack = [(root, False)]
        heights = {}

        while stack:
            node, visited = stack.pop()

            if node is None:
                continue

            if visited:
                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] = 1 + max(left_height, right_height)
            else:
                # Post-order: process children first, then node
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))

        return True

This iterative version achieves the same O(n) time complexity and O(n) space complexity while avoiding recursion entirely. The heights dictionary stores computed heights keyed by node identity.

Best Practices

Prefer the bottom-up approach: It runs in O(n) time and is concise. The top-down approach should only be used when you need to explain the concept at a high level.
Use sentinel values for early termination: Returning -1 to signal imbalance is a clean pattern that avoids redundant computation and keeps the code readable.
Handle edge cases explicitly: Always test with empty trees, single-node trees, and completely skewed trees. These edge cases frequently expose bugs.
Consider iterative solutions for production: In production code dealing with potentially deep trees, an iterative approach avoids stack overflow errors.
Separate tree construction from logic: Use helper functions like build_tree for testing. This keeps your solution focused on the algorithm itself.
Document your complexity: Always state both time and space complexity. Interviewers and reviewers expect this analysis.

Common Pitfalls

When implementing this solution, watch out for these frequent mistakes:

Checking only the root: A common error is to compute the height difference only at the root node. Remember that balance must hold at every node, not just the top.
Confusing height and depth: Height is the number of edges on the longest path from a node to a leaf. Depth is the number of edges from the root to a node. Make sure your height function computes height, not depth.
Forgetting the base case: An empty tree (None node) has height 0 and is trivially balanced. Omitting this check causes NoneType errors.
Inefficient height recomputation: If you call a separate height function at every node without memoization, you get O(n²) complexity. Always prefer the combined bottom-up approach.

Conclusion

Solving the Balanced Binary Tree problem is a foundational exercise that reinforces recursive thinking, tree traversal, and algorithm optimization. The journey from the naive top-down approach to the optimized bottom-up solution illustrates a common pattern in algorithm design: identifying overlapping subproblems and eliminating redundant work. By returning height information alongside balance status—and using a sentinel value for early termination—you can solve the problem in a single O(n) pass. Whether you are preparing for a coding interview or building production-grade tree algorithms, mastering this technique provides a solid foundation for tackling more advanced tree problems such as diameter of a binary tree, subtree validation, and self-balancing tree implementations.