Is the tree balanced

A tree is balanced when, at every node, the heights of its two subtrees differ by at most one. Say whether the given tree is balanced.

Worked example#

3 9 20 null null 15 7:

      3
     / \
    9   20
       /  \
      15   7

Nothing exceeds 1, so it is balanced.

Now 1 2 2 3 3 null null 4 4:

          1
        /   \
       2     2
      / \
     3   3
    / \
   4   4

At the root, the left side is 3 tall and the right is 1, a difference of 2. Not balanced.

Why "at every node" matters#

Checking only the root is not enough. A tree can have equal heights on each side of the root while one branch far below is badly lopsided. The definition is about every node, so the check has to be as well.

Doing it in one pass#

The slow way asks each node for its height, which recomputes the same heights over and over and costs O(n log n) at best and O(n squared) on a chain.

The better way makes one function return both answers at once: the height, and whether anything below was unbalanced. Use a height of -1 to mean "already unbalanced" and let it travel upward.

check(node):
    if node is missing, height 0
    left  = check(node.left);  if left is -1, return -1
    right = check(node.right); if right is -1, return -1
    if abs(left - right) > 1, return -1
    return 1 + max(left, right)

Every node is visited once, so O(n).

Constraints#

• 0 <= number of nodes <= 5000
• -10000 <= value <= 10000