Skip to main content

13. Balanced Binary Tree

easyAsked at Chegg

Determine if a binary tree is height-balanced — tests ability to combine depth computation with tree validation, relevant to Chegg's content-tree consistency checks.

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 one in which the left and right subtrees of every node differ in height by no more than 1. Return true if balanced, false otherwise.

Constraints

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

For each node, compute height of both subtrees separately — O(n^2) due to repeated work.

Time
O(n^2)
Space
O(n)
function height(node) {
  if (!node) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}
function isBalanced(root) {
  if (!root) return true;
  const lh = height(root.left);
  const rh = height(root.right);
  return Math.abs(lh - rh) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

Tradeoff:

2. Single-pass DFS with early exit

Return -1 as a sentinel for 'unbalanced' from the helper; propagate it upward to exit early without redundant height computations.

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

Tradeoff:

Chegg-specific tips

Chegg interviewers reward the single-pass sentinel trick; it shows you understand short-circuit evaluation, which maps well to validating nested educational content structures.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Chegg coding interview questions

See all Chegg problems →

Companies that also ask Balanced Binary Tree