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,

| Left Height - Right Height | ≤ 1

Brute Force Intuition

In an interview, you can explain it like this:

For every node, calculate the height of its left and right subtrees. If the height difference is more than 1, the tree is not balanced.

The drawback is that the height of the same subtree is computed repeatedly.

Complexity

• Time Complexity: O(N²)
• Space Complexity: O(H)

Brute Force Code

class Solution {

    public boolean isBalanced(TreeNode root) {

        if (root == null)
            return true;

        int leftHeight = height(root.left);

        int rightHeight = height(root.right);

        if (Math.abs(leftHeight - rightHeight) > 1)
            return false;

        return isBalanced(root.left) &&
               isBalanced(root.right);
    }

    private int height(TreeNode root) {

        if (root == null)
            return 0;

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

Moving Towards the Optimal Approach

Notice that while calculating:

Height

we can also determine whether the subtree is balanced.

Instead of returning only the height,

return:

-1

whenever an unbalanced subtree is found.

This allows us to stop checking further.

Pattern Recognition

Whenever you see:

• Balanced Tree
• Height Difference
• Height of Binary Tree

Think:

Postorder DFS

Key Observation

For every node:

Compute:

Left Height

↓

Right Height

If either subtree is already unbalanced:

Return -1

If:

|Left Height - Right Height| > 1

Again:

Return -1

Otherwise,

return the current height.

Optimal Approach

Step 1

Recursively compute:

Left Height

Step 2

Recursively compute:

Right Height

Step 3

If either returns:

-1

the tree is already unbalanced.

Step 4

If height difference exceeds:

1

return:

-1

Otherwise,

return:

1 + Math.max(leftHeight, rightHeight);

Optimal Java Solution

class Solution {

    public boolean isBalanced(TreeNode root) {

        return height(root) != -1;
    }

    private int height(TreeNode root) {

        if (root == null)
            return 0;

        int leftHeight = height(root.left);

        int rightHeight = height(root.right);

        if (leftHeight == -1 ||
            rightHeight == -1)
            return -1;

        if (Math.abs(leftHeight -
                     rightHeight) > 1)
            return -1;

        return 1 + Math.max(leftHeight,
                            rightHeight);
    }
}

Dry Run

        1
       / \
      2   3
     /
    4

Node 4

Left = 0

Right = 0

Height = 1

Node 2

Left = 1

Right = 0

Difference = 1

Balanced

Height = 2

Root 1

Left = 2

Right = 1

Difference = 1

Balanced

Answer:

true

Unbalanced Example

      1
     /
    2
   /
  3

Node 1:

Left Height = 2

Right Height = 0

Difference = 2

Return -1

Answer:

false

Why Returning -1 Works?

Instead of checking balance separately,

the recursion combines two tasks:

Compute Height

+

Detect Imbalance

The moment an unbalanced subtree is found,

-1 propagates upward,

avoiding unnecessary calculations.

Every node is visited exactly once.

Complexity Analysis

Where:

• N = Number of Nodes
• H = Height of the Tree

Interview One-Liner

Use postorder DFS to compute subtree heights, returning -1 whenever an imbalance is detected so the result propagates upward immediately.

Pattern Learned

Postorder DFS

↓

Left Height

↓

Right Height

↓

Check Difference

↓

Return Height

or

-1

Similar Problems

• Balanced Binary Tree
• Diameter of Binary Tree
• Maximum Depth of Binary Tree
• Binary Tree Maximum Path Sum
• Check Height Balanced Tree

Memory Trick

Think:

Go Left

↓

Go Right

↓

Difference > 1 ?

↓

Return -1

↓

Else Return Height

Mental Model

Leaf

↓

Returns Height

↓

Parent

↓

Checks Balance

↓

Returns Height

or

-1

Whenever you hear:

"Balanced Binary Tree"

your brain should immediately think:

Postorder DFS + Return Height or -1