Is Binary Tree Height-Balanced?

time: O(n)
space: O(h)
tags: trees · recursion · dfs

in the wild Sanity-check that an AVL / Red-Black implementation's rebalance step actually balanced — or detect when a workload pattern degenerates a self-balancing tree.

Problem

A binary tree is height-balanced if, at every node, the heights of the two child subtrees differ by at most 1. Given the root, return true if the tree is height-balanced; otherwise false. An empty tree is balanced.

Examples

        3
       / \             → true     (every node's left/right height differ by ≤ 1)
      9  20
         / \
        15  7

        1
       / \             → false    (the left subtree has height 3 vs right's height 0;
      2   2                       at node 1, |3 - 0| = 3 > 1)
     / \
    3   3
   / \
  4   4

   (empty)             → true
   (single node)       → true

Why this is the canonical "balanced-tree invariant" problem

This is the O(n) companion to the diameter trick — and it makes the same wrong-answer trap painfully obvious if you don't see it.

Naïve solution: at every node, compute |height(left) - height(right)| and check it's ≤ 1. That's O(n²) because computing height from each node re-walks its subtree.

The trick: one post-order pass that returns the height — and bails out with a sentinel as soon as imbalance is detected.

Two reasonable encodings:

Return an Option<height> / Option<int> / a special value (e.g. -1) to mean "imbalanced subtree below". As soon as a recursive call returns the sentinel, propagate it up without further work.
Return (height, balanced_flag) as a pair. Combine: balanced(self) = balanced(left) ∧ balanced(right) ∧ |h(left) - h(right)| ≤ 1.

Both work; both are O(n). Picking the sentinel approach makes "early exit" fall out for free.

This is exactly the proof-obligation of every self-balancing tree (AVL, Red-Black, Splay) — the rebalancing operation must preserve the invariant at every node. So is_balanced is what you'd add as a sanity-check in your AVL-rotation unit tests. The balanced trees lesson is the why; this is the check.

Hints

Hint 1 — why naïve is O(n²)

If at every node you call a fresh height() helper, each subtree is walked once for each of its ancestors — that's 1 + 2 + 4 + ... + n worth of work in the worst case → O(n²). Compute height once per subtree.

Hint 2 — bail out early

If any subtree is imbalanced, the whole tree is imbalanced — there's no point computing precise heights deeper. Return a sentinel "imbalanced" from the recursive call and propagate it without further work.

Hint 3 — pseudocode

def check(node):
    if node is None: return 0
    l = check(node.left)
    if l == -1: return -1
    r = check(node.right)
    if r == -1: return -1
    if abs(l - r) > 1: return -1
    return 1 + max(l, r)

-1 means "subtree (or this node) is unbalanced"; any other return is the subtree's height. The top-level answer is check(root) != -1.

Solution

from dataclasses import dataclass
from typing import Optional

@dataclass
class Node:
    val: int
    left:  Optional["Node"] = None
    right: Optional["Node"] = None

def is_balanced(root: Optional[Node]) -> bool:
    # Helper returns height, or -1 to signal "unbalanced — bail out".
    def check(n: Optional[Node]) -> int:
        if n is None:
            return 0
        l = check(n.left)
        if l == -1: return -1
        r = check(n.right)
        if r == -1: return -1
        if abs(l - r) > 1: return -1
        return 1 + max(l, r)
    return check(root) != -1

t1 = Node(3, Node(9), Node(20, Node(15), Node(7)))
t2 = Node(1, Node(2, Node(3, Node(4), Node(4)), Node(3)), Node(2))
t3 = None
t4 = Node(1)
cases = [(t1, True), (t2, False), (t3, True), (t4, True)]
for root, expected in cases:
    got  = is_balanced(root)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} is_balanced(...) = {got}  (expected {expected})")

class Node {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function isBalanced(root) {
  function check(n) {
    if (n === null) return 0;
    const l = check(n.left);
    if (l === -1) return -1;
    const r = check(n.right);
    if (r === -1) return -1;
    if (Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
  }
  return check(root) !== -1;
}

const t1 = new Node(3, new Node(9), new Node(20, new Node(15), new Node(7)));
const t2 = new Node(1,
            new Node(2, new Node(3, new Node(4), new Node(4)), new Node(3)),
            new Node(2));
const t3 = null;
const t4 = new Node(1);
const cases = [[t1, true], [t2, false], [t3, true], [t4, true]];
for (const [root, expected] of cases) {
  const got = isBalanced(root);
  console.log(`${got === expected ? "✓" : "✗"} isBalanced(...) = ${got}  (expected ${expected})`);
}

pub struct Node {
    pub val:   i32,
    pub left:  Option<Box<Node>>,
    pub right: Option<Box<Node>>,
}

pub fn is_balanced(root: &Option<Box<Node>>) -> bool {
    // Helper returns Some(height) or None when an unbalanced subtree is detected.
    fn check(n: &Option<Box<Node>>) -> Option<i32> {
        let Some(n) = n else { return Some(0); };
        let l = check(&n.left)?;
        let r = check(&n.right)?;
        if (l - r).abs() > 1 { return None; }
        Some(1 + l.max(r))
    }
    check(root).is_some()
}

fn leaf(v: i32) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: None, right: None }))
}
fn node(v: i32, l: Option<Box<Node>>, r: Option<Box<Node>>) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: l, right: r }))
}

fn main() {
    let t1 = node(3, leaf(9), node(20, leaf(15), leaf(7)));
    let t2 = node(1, node(2, node(3, leaf(4), leaf(4)), leaf(3)), leaf(2));
    let t3: Option<Box<Node>> = None;
    let t4 = leaf(1);
    let cases = [(&t1, true), (&t2, false), (&t3, true), (&t4, true)];
    for (root, expected) in cases {
        let got  = is_balanced(root);
        let mark = if got == expected { "✓" } else { "✗" };
        println!("{mark} is_balanced(...) = {}  (expected {})", got, expected);
    }
}

#include <algorithm>
#include <cstdlib>
#include <iostream>

struct Node {
    int   val;
    Node* left;
    Node* right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

// Returns height, or -1 to signal "unbalanced — bail out".
int check(Node* n) {
    if (!n) return 0;
    int l = check(n->left);
    if (l == -1) return -1;
    int r = check(n->right);
    if (r == -1) return -1;
    if (std::abs(l - r) > 1) return -1;
    return 1 + std::max(l, r);
}

bool is_balanced(Node* root) { return check(root) != -1; }

int main() {
    Node* t1 = new Node(3, new Node(9), new Node(20, new Node(15), new Node(7)));
    Node* t2 = new Node(1,
                new Node(2, new Node(3, new Node(4), new Node(4)), new Node(3)),
                new Node(2));
    Node* t3 = nullptr;
    Node* t4 = new Node(1);
    std::pair<Node*, bool> cases[] = { {t1, true}, {t2, false}, {t3, true}, {t4, true} };
    for (auto& [root, expected] : cases) {
        bool got = is_balanced(root);
        std::cout << (got == expected ? "✓" : "✗")
                  << " is_balanced(...) = " << (got ? "true" : "false")
                  << "  (expected " << (expected ? "true" : "false") << ")\n";
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int          val;
    struct Node* left;
    struct Node* right;
} Node;

static int iabs(int x)            { return x < 0 ? -x : x; }
static int imax(int a, int b)     { return a > b ? a : b; }

// Returns height, or -1 as a sentinel for "unbalanced — short-circuit upward".
static int check(Node* n) {
    if (!n) return 0;
    int l = check(n->left);
    if (l == -1) return -1;
    int r = check(n->right);
    if (r == -1) return -1;
    if (iabs(l - r) > 1) return -1;
    return 1 + imax(l, r);
}

bool is_balanced(Node* root) { return check(root) != -1; }

static Node* mk(int v, Node* l, Node* r) {
    Node* n = malloc(sizeof(Node));
    n->val = v; n->left = l; n->right = r;
    return n;
}

int main(void) {
    Node* t1 = mk(3, mk(9, NULL, NULL), mk(20, mk(15, NULL, NULL), mk(7, NULL, NULL)));
    Node* t2 = mk(1,
                mk(2, mk(3, mk(4, NULL, NULL), mk(4, NULL, NULL)), mk(3, NULL, NULL)),
                mk(2, NULL, NULL));
    Node* t3 = NULL;
    Node* t4 = mk(1, NULL, NULL);
    printf("%s is_balanced(t1) = %s  (expected true)\n",
           is_balanced(t1) ? "✓" : "✗", is_balanced(t1) ? "true" : "false");
    printf("%s is_balanced(t2) = %s  (expected false)\n",
           !is_balanced(t2) ? "✓" : "✗", is_balanced(t2) ? "true" : "false");
    printf("%s is_balanced(t3) = %s  (expected true)\n",
           is_balanced(t3) ? "✓" : "✗", is_balanced(t3) ? "true" : "false");
    printf("%s is_balanced(t4) = %s  (expected true)\n",
           is_balanced(t4) ? "✓" : "✗", is_balanced(t4) ? "true" : "false");
    return 0;
}

idle

The Rust version uses Option<i32> instead of a magic -1 — same idea, more typesafe. The ? operator makes the "bail out on imbalance" propagation a one-character noise. Every other language uses the -1 sentinel because they don't have such clean propagating Maybe syntax.

Complexity

Time: O(n) — single post-order pass. Each node visited once; O(1) work per node.
Space: O(h) recursion stack.
Naïve (don't do this): Calling height() from inside an outer traversal is O(n²). On a 100k-node tree that's catastrophic.

In the wild

AVL / Red-Black tree unit tests. After every rotation, the test asserts is_balanced(root) to verify the rebalancing logic didn't break the invariant.
Tree-data corruption checks. Random testing of tree mutations runs this between operations.
Debug assertions in self-balancing tree libraries — e.g. Linux kernel's rbtree has RB_CHECK_TREE (under CONFIG_DEBUG_*) that walks the entire tree to assert the Red-Black properties (which include a balance bound).
Visualizers that color "this subtree is unbalanced" — useful for teaching and for spotting regressions.

Variations

Return the imbalance witness. Instead of just true/false, return the offending node (the highest unbalanced one).
Stricter balance (height-balanced & weight-balanced). Some trees (e.g. weight-balanced BBSTs) need additional invariants. Same recursion, more conditions.
AVL-specific balance factor. Compute bf = h(left) - h(right) ∈ {-1, 0, 1} per node — but for the "is balanced" question, all you care about is the bound.
Color invariants on a Red-Black tree. Check that no red node has a red child, and that every root-to-leaf path has the same black-node count. Same recursive shape, different invariants tracked.