LeetCode 110: Balanced Binary Tree

Problem statement

Given the root of a binary tree, determine whether it is height-balanced.

A binary tree is balanced if for every node:

the height of the left subtree and right subtree differ by at most 1.

Formally, for each node: $|height(left) – height(right)| \le 1$ ∣height(left)−height(right)∣≤1

If this condition holds for all nodes, return true, otherwise return false.

Why this problem is tricky

Many people correctly check the height difference at the root, but the real rule says:

✅ Every node must satisfy the condition, not just the root.

So we must verify balance throughout the entire tree.

Key concepts

Height of a tree

Height is the number of nodes (or edges, depending on definition) on the longest path from a node down to a leaf.

Common coding definition used here:

height(null) = 0
height(node) = 1 + max(height(left), height(right))

Approach 1 (Naive): Check balance + compute height separately

A straightforward method:

For each node:
- compute height(left)
- compute height(right)
- check if difference ≤ 1
recursively check left and right subtrees too

Problem with this approach

Computing height() for every node repeats a lot of work.

In the worst case (skewed tree), complexity becomes:

O(n²)

Approach 2 (Optimized): Bottom-up DFS (Postorder) with early stopping

This is the standard best solution.

Core idea

Instead of computing heights again and again, we compute height once per node, while also detecting imbalance immediately.

We do a postorder traversal (left → right → node), because we need subtree heights before checking the current node.

Trick: Use a sentinel value

Return:

the height if subtree is balanced
-1 if subtree is unbalanced

Then:

if any child returns -1, immediately return -1
if abs(leftHeight - rightHeight) > 1, return -1
otherwise return 1 + max(leftHeight, rightHeight)

At the end:

if result is -1 → not balanced
else → balanced

Step-by-step logic

For each node:

Compute left subtree height
Compute right subtree height
If either is unbalanced → return -1
If height difference > 1 → return -1
Else return current height

This guarantees:

every node checked exactly once
imbalance propagates upward efficiently

Time and space complexity

Time

Each node is visited once:

O(n)

Space

Recursion stack depth = tree height:

O(h)
Worst case: O(n) (skewed)
Best/average: O(log n) (balanced tree)

Python solution (clean + interview-ready)

# Definition for a binary tree node.
# 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):
        def height(node):
            if not node:
                return 0

            left_h = height(node.left)
            if left_h == -1:
                return -1  # left subtree already unbalanced

            right_h = height(node.right)
            if right_h == -1:
                return -1  # right subtree already unbalanced

            if abs(left_h - right_h) > 1:
                return -1  # current node is unbalanced

            return 1 + max(left_h, right_h)

        return height(root) != -1

Python Alternative code solution

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> bool:
        def checkTreeBalance(root):
            if not root:
                return 0,True
            if not root.left and not root.right:
                return 1,True
            leftH=0
            rightH=0
            isBalancedL=True
            isBalancedR=True
            if root.left:
                leftH,isBalancedL = checkTreeBalance(root.left)
            if root.right:
                rightH,isBalancedR = checkTreeBalance(root.right)
            return max(leftH,rightH)+1,(isBalancedL and isBalancedR) and abs(leftH-rightH)<=1
        height,isBalanced = checkTreeBalance(root)
        return isBalanced

C++ solution

class Solution {
public:
    int height(TreeNode* root) {
        if (!root) return 0;

        int left = height(root->left);
        if (left == -1) return -1;

        int right = height(root->right);
        if (right == -1) return -1;

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

        return 1 + max(left, right);
    }

    bool isBalanced(TreeNode* root) {
        return height(root) != -1;
    }
};

Java solution

class Solution {
    private int height(TreeNode root) {
        if (root == null) return 0;

        int left = height(root.left);
        if (left == -1) return -1;

        int right = height(root.right);
        if (right == -1) return -1;

        if (Math.abs(left - right) > 1) return -1;

        return 1 + Math.max(left, right);
    }

    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
}

Quick example walkthrough

Consider:

Node 4: left=0 right=0 → height=1
Node 2: left=1 right=0 → diff=1 → height=2
Node 3: height=1
Node 1: left=2 right=1 → diff=1 → balanced ✅

Now if we add another node under 4:

Node 5 height=1
Node 4: left=1 right=0 → height=2
Node 2: left=2 right=0 → diff=2 ❌ → return -1 and stop early

Common mistakes to avoid

Checking balance only at the root (must check every node)
Using separate height calls causing O(n²)
Forgetting base case null -> height 0