Balanced Binary Tree

1. Define the problem

Given a binary tree, return true when it is height balanced . That means: for every single node in the tree, the height of its left side and the height of its right side differ by at most 1. The tree arrives as a level-order array such as [3, 9, 20, null, null, 15, 7], with null for a missing child. Your function builds the tree and returns true or false. The trick is to compute heights from the bottom up , and let a height of -1 mean "something below here is already unbalanced". That way you check the rule and measure the height in a single pass.

Constraints

The number of nodes is between 0 and 5000
-10⁴ ≤ node value ≤ 10⁴
Input is a level-order array with null for a missing child
An empty tree counts as balanced

Example

Inputvalues = [3, 9, 20, null, null, 15, 7]

Outputtrue

Explanation Node 9 is a leaf with height 1. Node 20 has two leaf children, so its height is 2 and its two sides differ by 0. At the root, the left side has height 1 and the right side has height 2, a difference of 1, which is allowed.

2. Know the words first

In plain terms

Height: The number of nodes on the longest downward path from a node to a leaf, counting the node itself. A leaf has height 1, and an empty spot has height 0.
Height balanced: Every node in the tree has a left side and a right side whose heights differ by no more than 1. One node breaking the rule makes the whole tree unbalanced.
Sentinel value: A special value used as a signal rather than as real data. Here -1 is a sentinel: a real height is never negative, so -1 can safely mean "unbalanced, stop looking".

3. Visualize the solution

Level-order slots; the label is the node value, the cell shows its measured height

3—

9—

20—

——

15—

7—

Statusinit

The tree is built; no height has been measured yet.

What happens in this step

values = [3, 9, 20, null, null, 15, 7]

Slot 0 holds 3, slots 1 and 2 hold 9 and 20.
Slots 3 and 4 are empty because 9 is a leaf.
Slots 5 and 6 hold 15 and 7, the children of 20.

Step 1 of 7

Steps to visualize

Each cell is one slot of the tree read level by level; a dash label means the slot is empty.
Heights are filled in from the bottom of the tree upwards, because a node cannot be measured before its children are.
A leaf has height 1. A node’s height is the taller of its two sides plus 1.
At every node, check that the two side heights differ by at most 1 before moving up.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Level-order slots; the label is the node value, the cell shows its measured height

3—

9—

20—

——

15—

7—

Statusinit

The tree is built; no height has been measured yet.

What happens in this step

values = [3, 9, 20, null, null, 15, 7]

Slot 0 holds 3, slots 1 and 2 hold 9 and 20.
Slots 3 and 4 are empty because 9 is a leaf.
Slots 5 and 6 hold 15 and 7, the children of 20.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function isBalanced(values) {
  function Node(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }

  function buildTree(list) {
    if (list.length === 0 || list[0] === null) {
      return null;
    }

    const root = new Node(list[0]);
    const queue = [root];
    let i = 1;

    while (i < list.length && queue.length > 0) {
      const node = queue.shift();

      if (list[i] !== null && list[i] !== undefined) {
        node.left = new Node(list[i]);
        queue.push(node.left);
      }

      i += 1;

      if (list[i] !== null && list[i] !== undefined) {
        node.right = new Node(list[i]);
        queue.push(node.right);
      }

      i += 1;
    }

    return root;
  }

  function height(node) {
    if (node === null) {
      return 0;
    }

    const left = height(node.left);
    const right = height(node.right);

    if (left === -1 || right === -1) {
      return -1;
    }

    if (Math.abs(left - right) > 1) {
      return -1;
    }

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

  return height(buildTree(values)) !== -1;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`values = [3, 9, 20, null, null, 15, 7]`	`true`	example from the docstring
`values = [1, 2, 2, 3, 3, null, null, 4, 4]`	`false`	the left side is two levels taller than the right
`values = []`	`true`	an empty tree is balanced
`values = [1, 2, null, 3]`	`false`	a chain of three nodes leaning left
`values = [1, 2, 3]`	`true`	a root with two leaves
`values = [1, 2, 3, 4, 5, 6, null, 8]`	`true`	an uneven tree where every difference is still at most 1

Balanced Binary Tree