EasyTreeDepth-First SearchBinary TreeUpdated Sep 2026

110. Balanced Binary Tree

Asked at Anduril

Difficulty

Easy

Time

O(n)

Space

O(h)

Pattern

Tree

Companies

1

Problem

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

A tree is height-balanced when, for every node, the heights of its left subtree and its right subtree differ by at most 1. The height of a subtree is the number of nodes on the longest path from that node down to a leaf. A missing child counts as height 0.

Return true if every node satisfies this rule, and false if even one node breaks it. An empty tree is balanced.

Check the height difference at every node

9leaf, h = 13|1 - 2| = 1 ok1520h = 27Node 3 has left height 1 and right height 2, so thedifference is 1 and the tree is balanced.
At each node we compare the height of the left subtree with the height of the right subtree, and the difference must be at most 1.

Constraints

  • ●The number of nodes in the tree is in the range [0, 5000].
  • ●-10^4 <= Node.val <= 10^4

Examples

Example 1
Inputroot = [3,9,20,null,null,15,7]
Outputtrue
WhyNode 9 and node 20 are leaves, so their subtrees both have height 1 and the difference at node 3 is 0. Node 20 has children 15 and 7, both leaves, so the difference there is also 0. Every node passes, so the answer is true.
Example 2
Inputroot = [1,2,2,3,3,null,null,4,4]
Outputfalse
WhyLook at node 2 (the left child of the root). Its left subtree goes 3 → 4 and has height 2, but its right subtree is just the node 3 with height 1. The difference is 1, which is fine. Now look at node 3 on the left: its left child is 4 with height 1, and it has no right child, so the difference is 1,
Example 3
Inputroot = []
Outputtrue
WhyThere are no nodes, so there is no node that can violate the rule. An empty tree is balanced by definition.

Asked At

1 companies
CompanyDifficulty
AndurilEasyView all Anduril questions →

How to Think About It

1

Naive approach: for each node, compute height(left) and height(right) and compare, then recurse into both children. Heights get recomputed for every ancestor, which is O(n²) on a skewed tree.

2

Key insight: compute height bottom-up (post-order), and have the same function report imbalance. Return the height if the subtree is balanced, or a sentinel like -1 if it is not.

3

At each node: get lh = h(left) and rh = h(right). If either is -1, or abs(lh - rh) > 1, return -1. Otherwise return 1 + max(lh, rh).

4

Once any subtree reports -1, every ancestor immediately passes it upward — this early exit is what makes the algorithm O(n).

5

Edge cases: an empty tree is balanced (height 0). A single node is balanced. A "vine" of three nodes going left is not.

Optimal Approach

Step 1: Define h(node):
If node is null, return 0.
lh = h(node.left); if lh == -1, return -1.
rh = h(node.right); if rh == -1, return -1.
If abs(lh - rh) > 1, return -1.
Return 1 + max(lh, rh).
Step 2: The tree is balanced iff h(root) != -1.

Each node is visited exactly once.

Time: O(n). Space: O(h) recursion stack, where h is the tree height.

Bottom-up height with a -1 sentinel

9h = 1315h = 1207h = 1Step 1 — leaves return height 1, since a leaf has nochildren.931 + max(1,2) = 315201 + max(1,1) = 27Step 2 — each parent adds 1 to the taller child, so node20 returns 2 and the root returns 3.null -> 0if |lh - rh| > 1: return -1else: return 1 + max(lh, rh)
The helper returns the height of a subtree, or -1 as soon as it finds an unbalanced node, and that -1 travels straight up to the root.
ComplexityTime O(n)Space O(h)Each node is visited once in a single post-order pass, and the recursion stack holds at most one root-to-leaf path, whose length is the tree height h.

What Trips People Up in Real Interviews

1

Only checking the root. The definition applies to every node — a tree whose root is balanced can still have an unbalanced subtree deep inside.

2

Writing the top-down O(n²) version and stopping there. Always mention that height and balance can be computed together in one post-order pass.

3

Confusing "balanced" with "complete" or "perfect". Balanced only restricts the height difference to at most one at each node.

4

Returning a tuple and forgetting to short-circuit. It is correct, but the -1 sentinel version is shorter and makes the early exit obvious.

Solution Code

O(n) time
def isBalanced(root):
    def h(node):
        if not node:
            return 0
        lh = h(node.left)
        if lh == -1:
            return -1
        rh = h(node.right)
        if rh == -1:
            return -1
        if abs(lh - rh) > 1:
            return -1
        return 1 + max(lh, rh)
    return h(root) != -1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Balanced Binary Tree problem?

Balanced Binary Tree asks whether a binary tree is height-balanced: for every node, the heights of its left and right subtrees differ by at most one. The interesting part is doing it in a single pass instead of recomputing heights over and over.

How do you solve Balanced Binary Tree?

The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Balanced Binary Tree?

Balanced Binary Tree is asked at Anduril. It is a easy difficulty problem.

What are common mistakes on Balanced Binary Tree?
  • Only checking the root. The definition applies to every node — a tree whose root is balanced can still have an unbalanced subtree deep inside.
  • Writing the top-down `O(n²)` version and stopping there. Always mention that height and balance can be computed together in one post-order pass.
  • Confusing "balanced" with "complete" or "perfect". Balanced only restricts the height difference to at most one at each node.
  • Returning a tuple and forgetting to short-circuit. It is correct, but the `-1` sentinel version is shorter and makes the early exit obvious.