Skip to main content

13. Balanced Binary Tree

easyAsked at Coursera

Determine whether a binary tree is height-balanced, a tree-depth problem Coursera uses to gauge clean recursive design.

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 left and right subtrees of every node differ in height by no more than one.

Constraints

  • Number of nodes 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

Approaches

1. Brute force (top-down)

For each node compute height separately, leading to O(n log n) due to repeated traversals.

Time
O(n log n)
Space
O(h)
function height(n) { return n ? 1 + Math.max(height(n.left), height(n.right)) : 0; }
function isBalanced(root) {
  if (!root) return true;
  return Math.abs(height(root.left) - height(root.right)) <= 1
    && isBalanced(root.left) && isBalanced(root.right);
}

Tradeoff:

2. Bottom-up DFS (O(n))

Return -1 as a sentinel for unbalanced subtrees while propagating height upward, achieving a single O(n) pass.

Time
O(n)
Space
O(h)
function check(node) {
  if (!node) return 0;
  const l = check(node.left);
  if (l === -1) return -1;
  const r = check(node.right);
  if (r === -1) return -1;
  if (Math.abs(l - r) > 1) return -1;
  return 1 + Math.max(l, r);
}
function isBalanced(root) { return check(root) !== -1; }

Tradeoff:

Coursera-specific tips

Coursera interviews emphasize algorithms for educational platforms, content recommendation systems, and scalable delivery pipelines. Medium-difficulty graph and DP problems are typical.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Balanced Binary Tree and other Coursera interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →