Balanced Binary Tree Solution Explained

Problem Statement

Given a binary tree, determine if it is height-balanced.

A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]

Output: false

Constraints:

The number of nodes in the tree is in the range [0, 5000]
-10⁴ <= Node.val <= 10⁴

Visual Idea Map

Think of checking balance like checking if a tower is stable. If one side is much taller than the other, the tower will topple. A balanced tree is "stable" at every level.

Step 1: Define Balance

A node is balanced if the height difference between its left and right subtrees is at most 1. The entire tree is balanced only if every node is balanced.

Step 2: Calculate Height Recursively

For each node, calculate the height of its left and right subtrees. Height = 1 + max(leftHeight, rightHeight). A null node has height 0.

Step 3: Check Balance at Each Node

At each node, check if |leftHeight - rightHeight| <= 1. If any node fails this check, the tree is not balanced.

Step 4: Early Termination (Optimization)

Instead of calculating height separately from checking balance, combine them. Return -1 (or a sentinel) when a subtree is unbalanced to propagate the failure up immediately.

Key Insight

The naive approach calculates height for each node separately (O(n²) worst case). The optimized approach combines height calculation with balance checking, achieving O(n) time by checking balance while calculating height.

Python Solution

Python O(n) time, O(h) space

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 checkHeight(node):
            # Base case: empty subtree has height 0
            if not node:
                return 0

            # Check left subtree, return -1 if unbalanced
            leftHeight = checkHeight(node.left)
            if leftHeight == -1:
                return -1

            # Check right subtree, return -1 if unbalanced
            rightHeight = checkHeight(node.right)
            if rightHeight == -1:
                return -1

            # Check balance at current node
            if abs(leftHeight - rightHeight) > 1:
                return -1

            # Return actual height
            return 1 + max(leftHeight, rightHeight)

        return checkHeight(root) != -1

Lines 1-5: Definition of TreeNode class with val, left, and right attributes.
Line 8: Main function that initiates the balance check. Returns True if checkHeight doesn't return -1.
Lines 9-10: Define nested helper function. An empty node (base case) has height 0.
Lines 13-16: Recursively check left subtree. If it returns -1 (unbalanced), propagate -1 upward immediately.
Lines 18-21: Recursively check right subtree. Same early termination logic.
Lines 23-25: At current node, check if left and right heights differ by more than 1. If so, return -1.
Lines 27-28: Return actual height: 1 (current node) + max of children's heights.

Java Solution

Java O(n) time, O(h) space

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }

    private int checkHeight(TreeNode node) {
        // Base case: empty subtree has height 0
        if (node == null) {
            return 0;
        }

        // Check left subtree
        int leftHeight = checkHeight(node.left);
        if (leftHeight == -1) {
            return -1;
        }

        // Check right subtree
        int rightHeight = checkHeight(node.right);
        if (rightHeight == -1) {
            return -1;
        }

        // Check balance at current node
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        // Return actual height
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Lines 1-11: TreeNode class definition with constructors.
Lines 14-16: Main method delegates to checkHeight, returns true if result isn't -1.
Lines 18-21: Base case: null node returns height 0.
Lines 24-27: Recursively get left subtree height, propagate -1 if unbalanced.
Lines 30-33: Recursively get right subtree height, propagate -1 if unbalanced.
Lines 36-38: Check balance condition using Math.abs() for absolute difference.
Line 41: Return height: 1 + max of children heights.

C++ Solution

C++ O(n) time, O(h) space

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return checkHeight(root) != -1;
    }

private:
    int checkHeight(TreeNode* node) {
        // Base case: empty subtree has height 0
        if (node == nullptr) {
            return 0;
        }

        // Check left subtree
        int leftHeight = checkHeight(node->left);
        if (leftHeight == -1) {
            return -1;
        }

        // Check right subtree
        int rightHeight = checkHeight(node->right);
        if (rightHeight == -1) {
            return -1;
        }

        // Check balance at current node
        if (abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        // Return actual height
        return 1 + max(leftHeight, rightHeight);
    }
};

Lines 1-8: TreeNode struct with constructors using initializer lists.
Lines 12-14: Main function calls checkHeight and compares result to -1.
Lines 17-20: Base case: nullptr returns 0 (empty subtree height).
Lines 23-26: Recursively check left subtree via node->left pointer.
Lines 29-32: Recursively check right subtree via node->right pointer.
Lines 35-37: Use abs() from <cstdlib> to check height difference.
Line 40: Return height using std::max from <algorithm>.

Complexity Analysis

Time Complexity: O(n)

Each node is visited exactly once. The algorithm computes height and checks balance in a single bottom-up pass. Unlike the naive O(n²) approach that calculates height separately for each node, we combine both operations.

Space Complexity: O(h)

The recursion stack uses O(h) space where h is the height of the tree. In the worst case (skewed tree), this becomes O(n). For a balanced tree, it's O(log n).

Why O(n) not O(n²)?

A naive approach would calculate height at each node separately: for each of n nodes, traverse up to O(n) nodes to find height. Our optimized approach uses bottom-up traversal with early termination — we compute height once per node and immediately return -1 if imbalance is detected, avoiding redundant work.

Edge Cases

1.

Empty Tree (root = null)

An empty tree is considered balanced. Returns true.

2.

Single Node Tree

A tree with only root has no children, so height difference is 0. Returns true.

3.

Completely Skewed Tree (Linked List)

A tree where each node has only one child. Maximum imbalance at root. Returns false.

4.

Deeply Nested Imbalance

Imbalance might occur deep in the tree. Early termination ensures we detect this without visiting remaining nodes.

Common Mistakes to Avoid

Mistake 1: Calculating height separately for each node

This leads to O(n²) time complexity. Always combine height calculation with balance checking in a single traversal.

Mistake 2: Forgetting to propagate -1 upward

If a subtree returns -1 (unbalanced), you must immediately return -1 without continuing to check other nodes.

Tip: Use a sentinel value

Using -1 as "unbalanced" is elegant because valid heights are always non-negative. This makes checking trivial: result == -1

Best Practice: Bottom-up approach

Post-order traversal (process children first, then current) is natural for this problem. You get children's heights before checking current node's balance.

Learn More

Want to dive deeper into the concepts behind tree properties and balance checking? Check out our comprehensive guide on SoftwareInLevels:

Understanding Tree Properties — From Basics to Advanced

This three-level series covers tree properties from beginner analogies to hardware-level optimization, including balance conditions, AVL trees, and more.

AlgoExplained.dev

Balanced Binary Tree