Binary Tree Height/Balance Check

Description

Three classic tree questions are one recursion in disguise. Is the tree height-balanced? How long is its longest path (the diameter)? What's its maximum path sum? Each one computes subtree heights from the bottom up. The only difference is the extra work at each node: passing an "unbalanced" signal up, or updating a best-so-far value from the two children's results. One pass, O(n), for all of them.

We'll go from simple to more technical:

1. The pattern: height with a -1 "unbalanced" signal.
2. Diameter: height plus a running best.
3. A second flavor: maximum path sum, clamping negative branches to zero.
4. The off-by-ones and lost signals that make these subtly wrong.

The approach: is the tree balanced?

A tree is height-balanced when, at every node, the two subtrees' heights differ by at most 1. Computing the height at each node separately would repeat work. Instead, compute heights bottom up as usual, and return -1 as a signal that something below is already unbalanced. Once a node sees -1, it passes it straight up without doing anything else.

Node 8 is never visited: the answer was known as soon as the left side returned -1.

int height(TreeNode node) {
    if (node == null) return 0;
    int left = height(node.left);
    if (left == -1) return -1;                    // already found imbalance below - propagate it up
    int right = height(node.right);
    if (right == -1) return -1;
    if (Math.abs(left - right) > 1) return -1;      // this node itself is imbalanced
    return Math.max(left, right) + 1;
}
// isBalanced(root) = height(root) != -1

def height(node: TreeNode | None) -> int:
    if node is None:
        return 0
    left = height(node.left)
    if left == -1:
        return -1                      # already found imbalance below - propagate it up
    right = height(node.right)
    if right == -1:
        return -1
    if abs(left - right) > 1:
        return -1                      # this node itself is imbalanced
    return max(left, right) + 1
# is_balanced(root) = height(root) != -1

Diameter: one extra line

The longest path between any two nodes bends at some node: it goes down the left side and down the right side. With heights counted in nodes, that path has left + right edges. So the diameter is the plain height function with one extra line before the return: diameter = max(diameter, left + right). In the tree above, the best bend is at the root: 3 + 1 = 4 edges, from 0 up to 5 and down to 8.

A second flavor: clamping a negative branch to zero

Maximum path sum has the same shape, with one new twist: values can be negative. Instead of a height, each call returns its gain: the best sum of a path that starts at this node and goes down. A branch whose gain is negative only lowers the total, so clamp it to 0, which means "don't go that way". At each node, the best path that bends there is the node's value plus both clamped gains.

int best = Integer.MIN_VALUE;
int maxGain(TreeNode node) {
    if (node == null) return 0;
    int leftGain = Math.max(maxGain(node.left), 0);    // clamp: never include a net-negative branch
    int rightGain = Math.max(maxGain(node.right), 0);
    best = Math.max(best, node.val + leftGain + rightGain);   // best path THROUGH this node
    return node.val + Math.max(leftGain, rightGain);           // best path continuing UP from this node
}

def max_path_sum(root: TreeNode | None) -> int:
    best = float("-inf")

    def max_gain(node: TreeNode | None) -> int:
        nonlocal best
        if node is None:
            return 0
        left_gain = max(max_gain(node.left), 0)     # clamp: never include a net-negative branch
        right_gain = max(max_gain(node.right), 0)
        best = max(best, node.val + left_gain + right_gain)   # best path THROUGH this node
        return node.val + max(left_gain, right_gain)           # best path continuing UP from this node

    max_gain(root)
    return best

Take a root of 2 with children -6 and 7, where -6 has a child 4 and 7 has children -1 and 3. The left branch's gain is -6 + 4 = -2, so it's clamped to 0. The best path is 2 + 7 + 3 = 12. Note that best itself may be negative, if every path in the tree is. Only the gain passed up to a parent is clamped.

Where you'll see it

The habit to keep is getting a second answer from a walk you're already doing. A checksum can be computed while serializing a structure, or a diameter while computing heights. On large structures walked often, skipping a second full pass adds up.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. One ancestor ignores the -1 from a child and computes its height normally. What's the risk?

2. A diameter uses left + right + 1, with heights counted in nodes. What's wrong?

3. A max path sum never clamps gains at 0. On a tree with only positive values, is the answer wrong?

Key takeaways

• Balance, diameter and maximum path sum are the same bottom-up height walk with different extra work.
• Pass the -1 "unbalanced" signal all the way up.
• With heights in nodes, left + right is the diameter in edges.
• In max path sum, clamp a negative gain to 0 before using it.
• The best overall value may be negative; the gain returned to a parent never is.