Balanced Binary Tree

easyTrees: Traversal50 stepsJava · Python · C++

A tree is height-balanced when, at every node, the two subtree heights differ by at most 1. Compute heights bottom-up and return -1 as soon as any subtree is unbalanced, so the whole check is one pass.

▶ Watch the animated trace

Traced input: root = [3, 9, 20, null, null, 15, 7] → true. Original problem: neetcode.io/problems/balanced-binary-tree

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(h)

Each node's height is computed once.

Key idea

Checking balance top-down with a separate height function is O(n²) on skewed trees.
Return height when balanced and -1 when not, in a single recursion.
Once a child reports -1, pass -1 straight up.

Common mistakes

Only checking the root's two subtrees; every node must be balanced.
Confusing balanced with complete or full.

Solution

Java

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

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

Python

def isBalanced(root: Optional[TreeNode]) -> bool:
    return height(root) != -1


def height(node: Optional[TreeNode]) -> int:
    if not node: return 0
    left = height(node.left)
    right = -1 if left == -1 else height(node.right)
    if left == -1 or right == -1 or abs(left - right) > 1: return -1
    return 1 + max(left, right)

C++

int height(TreeNode* node) {
    if (!node) return 0;
    int left = height(node->left);
    int right = left == -1 ? -1 : height(node->right);
    if (left == -1 || right == -1 || abs(left - right) > 1) return -1;
    return 1 + max(left, right);
}

bool isBalanced(TreeNode* root) {
    return height(root) != -1;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Unbalanced deep left At the root, left height 3 vs right height 1.	`root = [1, 2, 2, 3, 3, null, null, 4, 4]`	`false`
Empty tree An empty tree is balanced.	`root = []`	`true`
Chain of three At node 1: left 0, right 2.	`root = [1, null, 2, null, 3]`	`false`
Balanced everywhere except deep inside Node 2 has left height 2 and right height 0.	`root = [1, 2, 3, 4, null, null, null, 5]`	`false`