Typorithm · medium

Balanced Binary Tree

balanced-binary-treetreesbottom-upsentinelheight

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Balanced Binary Tree

Trees

A bottom-up DFS returns each node's height, or -1 as a sentinel for 'unbalanced', short-circuiting the rest of the tree.

A tree is height-balanced if every node's two subtrees differ in height by at most 1.

Compute heights bottom-up, but return -1 the moment any subtree is unbalanced.

The -1 sentinel propagates up and prunes further work, keeping it O(n) instead of O(n log n).

Return height, or -1 if unbalanced.

Check |left - right| <= 1.

Short-circuit on any -1.

function isBalanced(root) {
  function height(node) {
    if (node === null) {
      return 0;
    }
    const left = height(node.left);
    if (left === -1) {
      return -1;
    }
    const right = height(node.right);
    if (right === -1) {
      return -1;
    }
    if (Math.abs(left - right) > 1) {
      return -1;
    }
    return 1 + Math.max(left, right);
  }
  return height(root) !== -1;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Short-circuit left

A -1 from below means already unbalanced — stop early.

const left = height(node.left);
    if (left === -1) {
      return -1;
    }

2. Imbalance test

Subtree heights differing by more than 1 fail the balance rule.

if (Math.abs(left - right) > 1) {
      return -1;
    }

3. Return height

A balanced node reports its real height upward.

return 1 + Math.max(left, right)

4. Final verdict

Any -1 anywhere makes the whole tree unbalanced.

return height(root) !== -1

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.