Balanced Binary Tree

Easy Problem 68 of 151 Java and Python

Problem

Given a binary tree, determine whether it is height-balanced: for every node, the heights of its left and right subtrees differ by at most 1.

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
Why: The left subtree is two levels deeper than the right one.

Constraints

0 ≤ number of nodes ≤ 5000

Explanation

Checking each node with a fresh height computation repeats work. Instead, compute heights bottom-up, and use a special value (-1) to mean "this subtree is already unbalanced", which passes straight up to the root.

Approach 1 · Naive

Top-down height checks

Time O(n²) worst case
Space O(h)

At each node, compute both subtree heights from scratch, compare them, and recurse into the children.

If null, return true.
Check |height(left) - height(right)| <= 1, then recurse on both children.

Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(height(root.left) - height(root.right)) <= 1
            && isBalanced(root.left) && isBalanced(root.right);
    }

    private int height(TreeNode node) {
        return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right));
    }
}

Python

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node):
            return 0 if not node else 1 + max(height(node.left), height(node.right))

        if not root:
            return True
        return (abs(height(root.left) - height(root.right)) <= 1
                and self.isBalanced(root.left) and self.isBalanced(root.right))

Approach 2 · Optimal

Bottom-up with -1 for unbalanced

Time O(n)
Space O(h)

Return a subtree's height, or -1 if it is unbalanced anywhere inside.

check(null) = 0.
Get left and right; if either is -1 or they differ by more than 1, return -1.
Otherwise return 1 + max(left, right). The tree is balanced if the root is not -1.

Java

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

    private int check(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = check(node.left);
        int right = check(node.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return 1 + Math.max(left, right);
    }
}

Python

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def check(node):
            if not node:
                return 0
            left, right = check(node.left), check(node.right)
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            return 1 + max(left, right)

        return check(root) != -1

Complexity compared

Approach	Time	Space
Naive Top-down height checks	O(n²) worst case	O(h)
Optimal Bottom-up with -1 for unbalanced	O(n)	O(h)

Key takeaways

A sentinel return value (-1) lets one function answer two questions at once.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem