Balanced Binary Tree | Problems

Given a binary tree, determine if it is height-balanced. A balanced tree is one where the depth of the two subtrees of every node never differs by more than one.

Example: root = [3,9,20,null,null,15,7] → Output: true

Sample Input

—

Sample Output

—

Constraints

0 <= number of nodes <= 5000
-10^4 <= Node.val <= 10^4

Topics

Tree Binary Tree DFS

Bottom-Up DFS

Return height of each subtree, returning -1 if unbalanced.

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

Time: O(n) | Space: O(h)

Saved in this browser only. Private to you.