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

Enter fullscreen mode Exit fullscreen mode

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));
    }
}

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

Notice that while calculating:

Height

Enter fullscreen mode Exit fullscreen mode

we can also determine whether the subtree is balanced.

Instead of returning only the height,

return:

-1

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

If either subtree is already unbalanced:

Return -1

Enter fullscreen mode Exit fullscreen mode

If:

|Left Height - Right Height| > 1

Enter fullscreen mode Exit fullscreen mode

Again:

Return -1

Enter fullscreen mode Exit fullscreen mode

Otherwise,

return the current height.

Optimal Approach

Step 1

Recursively compute:

Left Height

Enter fullscreen mode Exit fullscreen mode

Step 2

Recursively compute:

Right Height

Enter fullscreen mode Exit fullscreen mode

Step 3

If either returns:

-1

Enter fullscreen mode Exit fullscreen mode

the tree is already unbalanced.

Step 4

If height difference exceeds:

1

Enter fullscreen mode Exit fullscreen mode

return:

-1

Enter fullscreen mode Exit fullscreen mode

Otherwise,

return:

1 + Math.max(leftHeight, rightHeight);

Enter fullscreen mode Exit fullscreen mode

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);
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

        1
       / \
      2   3
     /
    4

Enter fullscreen mode Exit fullscreen mode

Node 4

Left = 0

Right = 0

Height = 1

Enter fullscreen mode Exit fullscreen mode

Node 2

Left = 1

Right = 0

Difference = 1

Balanced

Height = 2

Enter fullscreen mode Exit fullscreen mode

Root 1

Left = 2

Right = 1

Difference = 1

Balanced

Enter fullscreen mode Exit fullscreen mode

Answer:

true

Enter fullscreen mode Exit fullscreen mode

Unbalanced Example

      1
     /
    2
   /
  3

Enter fullscreen mode Exit fullscreen mode

Node 1:

Left Height = 2

Right Height = 0

Difference = 2

Return -1

Enter fullscreen mode Exit fullscreen mode

Answer:

false

Enter fullscreen mode Exit fullscreen mode

Why Returning -1 Works?

Instead of checking balance separately,

the recursion combines two tasks:

Compute Height

+

Detect Imbalance

Enter fullscreen mode Exit fullscreen mode

The moment an unbalanced subtree is found,

-1 propagates upward,

avoiding unnecessary calculations.

Every node is visited exactly once.

Complexity Analysis

Metric Complexity Time Complexity O(N) Space Complexity O(H)

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Mental Model

Leaf

↓

Returns Height

↓

Parent

↓

Checks Balance

↓

Returns Height

or

-1

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Balanced Binary Tree”

your brain should immediately think:

Postorder DFS + Return Height or -1