Balanced Binary Tree

EasyTree DFSNeetCode 150JuniorOpen on LeetCodeUpdated Nov 11, 2026

You're given the root of a binary tree. Return true if it is height-balanced: at every node, the heights of the left and right subtrees differ by at most one. An empty tree is balanced.

Examples

root = [3,1,8,null,null,6,9] returns true

The root's left subtree has height 1 and its right subtree has height 2, a difference of one. Every other node is balanced too.

root = [1,2,null,3] returns false

The root's left subtree has height 2 and its right subtree is empty, so the heights differ by two.

root = [] returns true

An empty tree has no node that could be out of balance.

Constraints

0 <= number of nodes <= 5000
-10^4 <= Node.val <= 10^4

Hints

Hint 1

Checking balance at a node needs the heights of both of its subtrees. Can one traversal produce both the heights and the answer?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Compute heights bottom up with one post-order DFS and report imbalance through the return value. The helper returns a subtree's height, or -1 if any node inside it is unbalanced. At each node, get both child heights; if either is -1 or they differ by more than one, return -1, otherwise return 1 + the larger height. The tree is balanced when the root's result is not -1. The Python version runs the same post-order with an explicit stack, since a skewed tree of 5000 nodes is deeper than Python's default recursion limit. Each node is visited once: O(n) time, O(h) space.

Time

O(n)

Space

O(h)

Pitfall

Calling a separate height function at every node. It checks the right condition but recomputes heights over and over, which is O(n^2) on a skewed tree.

Solutions

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

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

from typing import Optional

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        height = {None: 0}
        stack = [(root, False)]
        while stack:
            node, children_done = stack.pop()
            if node is None:
                continue
            if children_done:
                left, right = height[node.left], height[node.right]
                if abs(left - right) > 1:
                    return False
                height[node] = 1 + max(left, right)
            else:
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))
        return True