Balanced Binary Tree Easy 0 attempts
LeetCode ↗

Balanced Binary Tree

Easy TreeBinary TreeDFS LeetCode

You're given the root of a binary tree. Determine whether it's height-balanced — meaning that for every node in the tree, the heights of its left and right subtrees differ by at most one.

Input Format
Implement isBalanced(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 3

Input
root = []
Output
true
Constraints
  • 0 <= number of nodes <= 5000
  • -10^4 <= Node.val <= 10^4
Test Cases (3)
Case 1
Args: [[3,9,20,null,null,15,7]] Expected: true
Case 2
Args: [[1,2,2,3,3,null,null,4,4]] Expected: false
Case 3
Args: [[]] Expected: true
Topics
TreeBinary TreeDFS

Iterative Postorder

Compute child heights before parent heights. Reject any node whose child heights differ by more than one.

javascript
function isBalanced(root) {
  if(!root)return true;
  const stack=[[root,false]],heights=new Map();
  while(stack.length) {
    const [node,done]=stack.pop();
    if(!done){stack.push([node,true]);if(node.right)stack.push([node.right,false]);if(node.left)stack.push([node.left,false]);}
    else {const l=heights.get(node.left)||0,r=heights.get(node.right)||0;if(Math.abs(l-r)>1)return false;heights.set(node,1+Math.max(l,r));}
  }
  return true;
}

Time: O(n) | Space: O(n) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript