Balanced Binary Tree

L7 Medium Trees

Concept

A tree is height-balanced when every node's left and right subtrees differ by at most one in height. Detecting it recursively means computing heights bottom-up.

Given the root of a binary tree, return true if, for every node, the heights of its two children differ by at most 1.

Examples

▸ root = [3, 9, 20, nil, nil, 15, 7]

→ true

▸ root = [1, 2, 2, 3, 3, nil, nil, 4, 4]

→ false

▸ root = []

→ true

Progressive Hints

Hint 1 · Nudge

One helper can both measure height and report 'unbalanced' as a special value.

Hint 2 · Plan

Write a helper that returns a subtree's height, but returns a sentinel such as -1 the moment any subtree is unbalanced. The tree is balanced when the helper at the root never returns that sentinel.

Hint 3 · Approach

height(node): if nil return 0; l = height(left); r = height(right); if l or r is -1, or the gap between them is over 1, return -1; otherwise return 1 + max(l, r). Return height(root) != -1.

Output

// Run your code to see the output here.