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
// 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;
};