Skip to main content

110. Balanced Binary Tree

easy

Determine whether a binary tree is height-balanced — every node's two subtrees differ in height by at most 1. The naive O(n^2) recursion screams for optimization; the post-order trick collapses it to O(n).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Constraints

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

Examples

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
true

Example 2

Input
root = [1,2,2,3,3,null,null,4,4]
Output
false

Example 3

Input
root = []
Output
true

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive: at each node, compute left height, right height, compare, recurse. That's O(n^2) because height is recomputed.

Hint 2

Better: compute height once with a single post-order pass. Use a sentinel (e.g., -1) to signal 'unbalanced detected below'.

Hint 3

If either subtree returns the sentinel, propagate immediately — no further work needed.

Solution approach

Reveal approach

Post-order DFS that returns height while early-aborting on imbalance. Helper check(node): if node is null return 0. Compute left = check(node.left); if left == -1 return -1. Compute right = check(node.right); if right == -1 return -1. If abs(left - right) > 1 return -1. Otherwise return 1 + max(left, right). Top-level returns check(root) != -1. The -1 sentinel short-circuits all higher frames once any subtree is unbalanced, giving O(n) total work. O(n) time, O(h) recursion space.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • tree-dfs
  • recursion
  • post-order

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Balanced Binary Tree and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →