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

Topic	Description
Trees	Hierarchical nodes with parent–child links for ordered and nested data.
Invert Binary Tree	Swap every node’s two children so the tree becomes its own mirror image.
Same Tree	Walk two trees side by side and report whether they have the same shape and the same values.
Symmetric Tree	Check whether a tree folds onto itself by comparing mirror pairs from the two halves.
Binary Tree Right Side View	Walk the tree level by level and collect the last node of each level, the ones visible from the right.
Binary Tree Zigzag Level Order Traversal	Read the tree one level at a time, reversing every other level so the values snake down the tree.