Balanced Binary Tree

Ishaan S Published 24 Oct, 2026

You are given the root of a binary tree. Decide whether it is height-balanced.

A tree is height-balanced when, at every node, the heights of its left and right subtrees differ by at most 1. The height of a subtree is the number of nodes on its longest downward path, so an empty subtree has height 0 and a single node has height 1.

Return true if the tree is height-balanced and false otherwise. An empty tree is balanced.

Trees are written in level order: the root first, then each level from left to right, with null marking a missing child. For example [4,2,null,1] is a root 4 whose left child 2 has a left child 1.

Example 1

Input: root = [3,1,8,null,2,6,9] Output: true Why: Every node's two subtrees differ in height by at most one.

Example 2

Input: root = [1,2,null,3] Output: false Why: Node 2 has a left subtree of height 1 and no right subtree, but the root has a left subtree of height 2 and an empty right subtree.

Example 3

Input: root = [1,2,3,4,null,null,5,6,null,null,7] Output: false Why: At the root the two sides have equal height, but node 2 has a left subtree of height 2 and no right subtree, so the tree is not balanced.

Constraints

0 <= number of nodes <= 5000
-10⁴ <= Node.val <= 10⁴
The depth of the tree is at most 100.

Pattern Path · Trees: DFS · problem 81 of 169

Checking only the root is not enough: the condition must hold at every node.

To check a node you need the heights of its two subtrees. Computing heights again for every node repeats a lot of work.

Do one post-order pass that returns each subtree's height, and a special value such as -1 as soon as any subtree is found to be unbalanced.

Target: O(n) time, O(h) extra space.

Start simple

For every node, compute the heights of both subtrees from scratch and compare them: O(n²) time on a skewed tree (O(n log n) on a balanced one).

The key idea

The balance condition at a node needs exactly one fact from each child: its height. Heights are naturally computed bottom-up, since a node's height is 1 + max(left height, right height). So compute heights in a post-order traversal and check the balance condition at the same time.

Let the helper return the height of a subtree, or -1 to mean "somewhere inside, this subtree is unbalanced". At each node:

get the left result; if it is -1, pass -1 straight up without exploring further;
get the right result and do the same;
if the two heights differ by more than 1, return -1; otherwise return the node's height.

The tree is balanced exactly when the root's result is not -1. Each node is visited once, so the time is linear, compared with recomputing heights from every node. The recursion uses stack space proportional to the tree's height.

Complexity

Time: O(n)
Space: O(h)

Python

class Solution:
    def isBalanced(self, root):
        def height(node):
            """Height of the subtree, or -1 if it is unbalanced somewhere inside."""
            if node is None:
                return 0
            left = height(node.left)
            if left == -1:
                return -1
            right = height(node.right)
            if right == -1 or abs(left - right) > 1:
                return -1
            return 1 + max(left, right)

        return height(root) != -1

JavaScript

var isBalanced = function(root) {
  // Height of the subtree, or -1 if it is unbalanced somewhere inside.
  const height = (node) => {
    if (node === null) return 0;
    const left = height(node.left);
    if (left === -1) return -1;
    const right = height(node.right);
    if (right === -1 || Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left, right);
  };
  return height(root) !== -1;
};

What the interviewer is checking

The interviewer wants to see whether you notice the repeated height computations of the naive solution and fuse the check into a single bottom-up pass that returns more than a boolean.

Mistakes to avoid

Only comparing the heights of the root's two subtrees; an imbalance can hide deeper in the tree.
Calling a separate height function from every node, which is quadratic on skewed trees.
Confusing height with the number of edges and getting the empty-subtree base case wrong. Any consistent convention works if used everywhere.

Follow-ups to expect

How would you rebalance an unbalanced BST? (In-order list, rebuild from the middle.)
How do AVL trees keep this property after inserts? (Store heights, rotate on imbalance.)
Can you return the first unbalanced node instead? (Report it from the bottom-up pass.)

In real software

Self-balancing search trees in databases and language libraries (AVL and red-black trees) maintain a balance invariant like this one so that lookups stay logarithmic.

Practice next

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        return false;
    }
}

public class Main {
    // Builds a tree from a level-order array where null marks a missing child.
    static TreeNode build(Integer[] a) {
        if (a.length == 0 || a[0] == null) return null;
        TreeNode root = new TreeNode(a[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < a.length) {
            TreeNode n = q.poll();
            if (i < a.length && a[i] != null) { n.left = new TreeNode(a[i]); q.add(n.left); }
            i++;
            if (i < a.length && a[i] != null) { n.right = new TreeNode(a[i]); q.add(n.right); }
            i++;
        }
        return root;
    }

public static void main(String[] args) {
        TreeNode root = build(new Integer[]{3, 1, 8, null, 2, 6, 9});
        System.out.println(new Solution().isBalanced(root)); // true
    }
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return false;
    }
};

// Builds a tree from a level-order list where NIL marks a missing child.
const int NIL = INT_MIN;
TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == NIL) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < a.size()) {
        TreeNode* n = q.front(); q.pop();
        if (i < a.size() && a[i] != NIL) { n->left = new TreeNode(a[i]); q.push(n->left); }
        i++;
        if (i < a.size() && a[i] != NIL) { n->right = new TreeNode(a[i]); q.push(n->right); }
        i++;
    }
    return root;
}

int main() {
    TreeNode* root = build({3, 1, 8, NIL, 2, 6, 9});
    cout << boolalpha << Solution().isBalanced(root) << endl;  // true
}

Topics #081 #t-tree-dfs DFS Easy Practice Recursion Tree