Check if a binary tree is height-balanced

A post-order height check that stops early the moment any subtree is found unbalanced.

The idea

A tree is height-balanced when, at every node, the heights of its left and right subtrees differ by at most 1. Computing height bottom-up already visits every node once, so piggyback the balance check onto it: have each call return -1 the instant it or a subtree below it is unbalanced, so no later work wastes time on a tree that has already failed.

Code

public static int CheckHeight(TreeNode node) {
    if (node == null) return 0;
    int left = CheckHeight(node.left);
    if (left == -1) return -1;
    int right = CheckHeight(node.right);
    if (right == -1) return -1;
    if (Math.Abs(left - right) > 1) return -1;
    return 1 + Math.Max(left, right);
}

Tips

• A naive version recomputes height for every node from scratch, costing O(n²) on a skewed tree. The -1 sentinel keeps it O(n).
• Try a long chain of inserts (sorted keys) to see an unbalanced tree.

In the .NET library

This -1-sentinel trick (fold a yes/no check into a value-returning computation) shows up again whenever a bottom-up pass needs to bail out early, such as validating a BST.