Coding interview problems › Trees & BSTs

🌳 Trees & BSTs Easy

Balanced Binary Tree

Check if a binary tree is height-balanced: the O(n) bottom-up trick that returns height and balance together, tested Python code, mistakes and a live visual.

Also searched as: check if a binary tree is height balanced · height-balanced tree in O(n)

🌳

Try it live Free

Binary Search Tree & Traversals

Insert values in sorted order in the BST lab to grow a lopsided chain, then a shuffled order to see a much more balanced shape.

Open the playground →

The problem

A binary tree is height-balanced if, at every node, the heights of the left and right subtrees differ by at most 1. Given the root, return whether the tree is balanced.

Inputroot = [3, 9, 20, null, null, 15, 7]
OutputTrue
Inputroot = [1, 2, 2, 3, 3, null, null, 4, 4]
OutputFalse

The left subtree is two levels taller than the right.

The key insight

The naive approach recomputes heights from scratch at every node. Instead, compute height bottom-up once and let each call report two things: its height, or a special value (like -1) meaning "already unbalanced below me". As soon as any subtree is unbalanced, the signal propagates straight to the top.

Brute force first: Calling a separate height() function at every node and comparing the results is correct but O(n²) on a skewed tree, since heights get recomputed again and again.

Step-by-step approach

  1. Write height(node) that returns 0 for None.
  2. Get the left height; if it is -1, return -1 immediately. Do the same for the right.
  3. If the two heights differ by more than 1, return -1.
  4. Otherwise return 1 + max(left, right).
  5. The tree is balanced exactly when height(root) != -1.

Python solution

PYTHON 3tested
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def is_balanced(root):
    def height(node):                  # -1 means "unbalanced somewhere below"
        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

Complexity

TimeO(n)
SpaceO(h)

Each node is visited once and does constant work with its children's heights. The recursion stack is the tree height h.

Common mistakes

Frequently asked questions

What is the time and space complexity of checking if a tree is balanced?

With the bottom-up height trick it is O(n) time and O(h) space for the recursion stack. The top-down version that calls height() at every node is O(n²) in the worst case.

Why does balance matter?

Search, insert and delete in a binary search tree cost O(h). A balanced tree keeps h near log n; a degenerate one makes those operations O(n), which is why AVL and red-black trees rebalance themselves.

Can I return a tuple instead of using -1?

Yes, returning (is_balanced, height) from each call is equally correct and some find it clearer. The -1 sentinel just avoids building tuples.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Trees & BSTs Binary Search Tree & Traversals lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.