Balanced Binary Tree: Multiple Solutions and Complexity Analysis

A balanced binary tree is a binary tree data structure that maintains a height close to the minimum possible for the number of nodes it contains. In a balanced tree, the heights of the left and right subtrees of every node differ by at most a constant factor (often 1 for height‑balanced trees). Common variants include AVL trees (height difference ≤ 1) and Red‑Black trees (height difference ≤ 2 * log₂(n) in practice). This tutorial focuses on the height‑balanced property (often simply called “balanced” in coding interviews) and explores multiple ways to determine whether a given binary tree satisfies that property.

What is a Balanced Binary Tree?

A binary tree is height‑balanced if for every node, the absolute difference between the heights of its left and right subtrees is at most 1. This is the definition used in the classic “Balanced Binary Tree” problem (LeetCode 110). The height of a node is the number of edges on the longest path from that node to a leaf. An empty tree (null) is considered balanced and has height -1 (or 0 depending on convention; we'll use -1 for empty).

Formally:

An empty tree is balanced.
For a node with left subtree height hL and right subtree height hR, it is balanced iff |hL - hR| ≤ 1 and both left and right subtrees are themselves balanced.

Why It Matters

Balancing directly impacts the performance of operations on binary search trees (BSTs). An unbalanced BST can degrade to a linked list, making search, insertion, and deletion O(n) instead of O(log n). Self‑balancing trees (AVL, Red‑Black) maintain balance automatically, guaranteeing O(log n) time complexity. Understanding how to verify balance helps you implement or debug such trees and is a common interview topic to test recursion and tree traversal skills.

Multiple Solutions for Checking Balance

We will explore three approaches:

Top‑Down Recursion (Naive) – computes height separately for each node.
Bottom‑Up Recursion with Early Exit – computes height and balance in a single traversal.
Iterative Post‑Order Traversal – uses a stack to simulate recursion (less common but useful for avoiding recursion depth limits).

We will implement each in Python and analyze time and space complexity.

1. Top‑Down Recursion (Naive)

This approach directly follows the definition: for each node, compute the height of its left and right subtrees, check the difference, and then recursively verify that both children are balanced. It is simple but performs repeated work because heights are recalculated many times.

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

def height(node: TreeNode) -> int:
    """Return height of node (edges to deepest leaf)."""
    if not node:
        return -1
    return 1 + max(height(node.left), height(node.right))

def isBalanced_topdown(root: TreeNode) -> bool:
    if not root:
        return True
    left_h = height(root.left)
    right_h = height(root.right)
    if abs(left_h - right_h) > 1:
        return False
    return isBalanced_topdown(root.left) and isBalanced_topdown(root.right)

Complexity Analysis (Top‑Down)

Time: O(n²) in the worst case. For a skewed tree, the height function is called many times on overlapping subtrees. Each call visits every node in its subtree, leading to O(n) per node and O(n²) total.
Space: O(n) for the recursion stack (worst‑case tree depth = n).

2. Bottom‑Up Recursion (Optimal)

Instead of computing heights separately, we combine the height and balance check into one recursive function. The function returns the height of the subtree if it is balanced, or a sentinel value (e.g., -2) to indicate imbalance. This eliminates redundant height calculations and yields O(n) time.

def isBalanced_bottomup(root: TreeNode) -> bool:
    def check(node: TreeNode) -> int:
        """Return height if balanced, else -2."""
        if not node:
            return -1
        left_h = check(node.left)
        if left_h == -2:
            return -2
        right_h = check(node.right)
        if right_h == -2:
            return -2
        if abs(left_h - right_h) > 1:
            return -2
        return 1 + max(left_h, right_h)
    
    return check(root) != -2

Complexity Analysis (Bottom‑Up)

Time: O(n) – each node is visited exactly once. The height computation is folded into the traversal.
Space: O(n) for recursion stack (worst‑case depth). For a balanced tree it is O(log n).

3. Iterative Post‑Order Traversal

To avoid recursion depth limits (especially in languages with limited call stack or for very deep trees), we can implement an iterative post‑order traversal using a stack. We store for each node its height and whether it has been processed. This is more verbose but demonstrates a useful technique.

def isBalanced_iterative(root: TreeNode) -> bool:
    if not root:
        return True
    stack = [(root, False)]  # (node, visited_children)
    heights = {}  # node -> height
    while stack:
        node, visited = stack.pop()
        if visited:
            left_h = heights.get(node.left, -1)
            right_h = heights.get(node.right, -1)
            if abs(left_h - right_h) > 1:
                return False
            heights[node] = 1 + max(left_h, right_h)
        else:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return True

Complexity Analysis (Iterative)

Time: O(n) – each node pushed and popped once.
Space: O(n) for the stack and the height dictionary. In practice, the recursion version is simpler and equally efficient unless stack depth is a concern.

Practical Example and Test

Let's test all three implementations on a simple tree:

# Construct a tree:
#       1
#      / \
#     2   3
#    / \
#   4   5
#  /
# 6
tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.left.left = TreeNode(4)
tree.left.right = TreeNode(5)
tree.left.left.left = TreeNode(6)

print("Top-down:", isBalanced_topdown(tree))   # False (height diff at node 2: left=2, right=0)
print("Bottom-up:", isBalanced_bottomup(tree)) # False
print("Iterative:", isBalanced_iterative(tree))# False

Which Solution to Choose?

Interview / coding challenges: The bottom‑up recursion is the gold standard – clear, efficient, and easy to explain. It demonstrates understanding of recursion and early termination.
Production code: The bottom‑up approach is also preferred