Skip to content
Shubham JangleResources
Trees

Explore topics

Balanced Binary Tree

Problem

A binary tree is height-balanced if every node's two subtree heights differ by at most one. Return whether the entire tree is balanced.

Approach and revision checks

The helper returns a subtree height or -1 for an imbalance. Propagating the sentinel avoids recomputing heights for each node: O(n) time and O(h) recursion space, O(n) in the skewed worst case. The empty tree is balanced. Test a balanced root whose deeper subtree is unbalanced; checking only the root is insufficient.

Original repository source

Copied from the supplied local DSA-Series checkout; code and comments are preserved. Run alternative definitions separately when comparing approaches.

14-balanced-binary-tree.js

Original file on GitHub

// Optimised TC: O(N) SC: O(N) stack space
function dfs(root) {
  if (!root) return 0;

  let left = dfs(root.left);
  let right = dfs(root.right);

  if (left === -1 || right === -1) return -1;
  if (Math.abs(left - right) > 1) return -1;

  return Math.max(left, right) + 1;
}

var isBalanced = function (root) {
  if (!root) return true;

  if (dfs(root) === -1) return false;
  return true;
};