Introduction

To check whether a binary tree is balanced, compare the height of its left side with the height of its right side. The project uses -1 as a quick signal that a lower part of the tree has already failed the check.

The main idea is straightforward. If the two sides of every node are close enough in height, the tree is considered balanced. If one side becomes much deeper than the other, the tree is unbalanced.

Balance is a height relationship

For this article, a node is balanced when the heights of its left and right subtrees differ by no more than one. Height means the number of links on the longest path from a node down to a leaf. A subtree is a node together with the nodes below it. The repository’s isBalanced() method applies this condition to every node by using recursion.

For example, a node whose left side has height 2 and right side has height 1 is balanced because the difference is 1. A node whose sides have heights 3 and 0 is not balanced because the difference is 3.

This is not the same as checking whether a tree is complete, full, or perfect. Those terms describe different shape properties.

The interesting implementation detail is that the private helper returns two kinds of result:

  • a non-negative height when the subtree is balanced; or
  • -1 when the subtree is already unbalanced.

This use of -1 is called a sentinel value. A sentinel is a special value with a meaning different from the normal result. In this case, normal non-negative numbers represent heights, while -1 means “an imbalance was found.”

The public method checks whether the final result is -1.

A tree with one balanced branch and one branch whose child heights differ by more than one

The expensive approach

A straightforward balance check can calculate the height of the left subtree, calculate the height of the right subtree, compare them, and repeat those height calculations at every node. Because the same descendants may be measured again from multiple ancestors, a skewed tree can cause repeated work.

The repository avoids that pattern. Its helper performs a postorder-style calculation. This means the children are evaluated before the current node. Each child effectively reports either its height or the failure signal, so the parent can decide what to return.

How the sentinel propagates

The control flow is compact:

The height-sentinel helper flow from child checks to either a height or -1

In pseudocode, the mental model is:

if subtree is empty: return 0
leftHeight = check(left)
rightHeight = check(right)
if either height is -1: return -1
if absolute difference exceeds 1: return -1
return 1 + maximum(leftHeight, rightHeight)

The source uses 0 for an empty subtree in this balance helper. That is separate from the tree’s height() method, which defines an empty subtree as -1 so that a leaf has height 0. Mixing those conventions would make the balance comparison harder to reason about, so the helper’s local convention matters.

What the sentinel saves

The source evaluates both child subtrees before checking whether either returned -1. The sentinel does not make this implementation skip the sibling subtree: it lets the current node return failure instead of comparing heights or producing a normal height, and it carries that result to its parent.

When both child results are valid, the helper applies the exact condition Math.abs(left - right) > 1. A valid node returns one plus the larger child height. Each node is evaluated once, giving O(n) time and O(h) recursion stack space for n nodes and height h.

A small trace

Consider a branch where a node’s left subtree has height 2 and its right subtree has height 0. The difference is 2, so that node returns -1. Its parent still evaluates both child calls, then receives the sentinel and returns -1 without comparing valid heights or producing a normal height. The public method ultimately reports false.

This is a demonstrated control-flow example based on the repository’s helper; it is not a measured benchmark.

What “balanced” does not promise

  • Complete: every level except possibly the last is full, with the final level filled from the left.
  • Full: every node has either zero or two children.
  • Perfect: every internal node has two children and all leaves share a depth.
  • Height-balanced: the project’s local height-difference rule holds at every node.

A tree may be height-balanced without being complete or perfect. Keeping the definitions separate prevents a useful sentinel-based check from being treated as a general shape validator.

Reflection

The sentinel is a small example of returning more information through one value. The helper does not need a separate “found imbalance” flag passed through every call: -1 is the failure signal, while non-negative values remain usable heights. The sentinel makes the one-pass calculation visible in the control flow rather than hiding it in a second traversal.

Key takeaways

  • This repository defines balance as a height difference of at most one at every node.
  • Its helper returns a subtree height or -1 when imbalance is detected.
  • Postorder evaluation visits both children once, then lets failure propagate upward without a separate height traversal.
  • The resulting balance check is O(n) time with O(h) recursion space.
  • Balanced, complete, full, and perfect describe different tree properties.

Sources