Skip to content
EasyTreesAI interview only

Balanced Binary Tree

Asked atamazongooglemetamicrosoftbloomberg

01 · Problem

Given the root of a binary tree, decide whether it is height-balanced. A tree is height-balanced when, at every node, the heights of its left and right subtrees differ by no more than one.

Return true if the tree is height-balanced and false otherwise. The tree is given in level-order, with null marking a missing child. An empty tree counts as balanced.

02 · Examples

Example 01
    3
   / \
  9  20
    /  \
   15   7
Input
root = [3,9,20,null,null,15,7]
Output
true

At the root the subtree heights are 1 and 2; every other node is also within one.

Example 02
        1
       / \
      2   2
     / \
    3   3
   / \
  4   4
Input
root = [1,2,2,3,3,null,null,4,4]
Output
false

At the root the left subtree has height 3 and the right subtree has height 1, a difference of 2.

Example 03
Input
root = []
Output
true

An empty tree has no nodes that could be unbalanced.

03 · Constraints

  • 01The number of nodes in the tree is in the range [0, 100].
  • 02-104 <= Node.val <= 104
  • 03Height is measured in nodes; an empty subtree has height 0.
  • 04The tree height is at most 100, and the tree may be fully skewed.

04 · Optimal complexity

Time
O(n)
Space
O(h)
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem