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 Sam K., 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

More Trees practice problems

See all Trees problems →