3.17

A binary tree is height-balanced if for every node the heights of its left and right sub-trees differ by at most 1. The key to an [math]O(n)[/math] solution is to compute the height of every sub-tree only once while simultaneously checking balance:
function check(node):
if node = null: # empty sub-tree
return 0 # height = 0, still balanced

hL = check(node.left) # height of left
if hL = −1: # left sub-tree already imbalanced
return −1

hR = check(node.right) # height of right
if hR = −1: # right sub-tree already imbalanced
return −1

if |hL − hR| > 1: # current node violates balance
return −1 # propagate failure flag upward

return max(hL, hR) + 1 # height of current sub-tree
Algorithm: 1. Call check(root). 2. If the result is −1 the tree is not height-balanced; otherwise it is. Correctness: • The height of each sub-tree is computed exactly once (post-order). • A flag −1 is propagated upward as soon as any imbalance is found, so every node reports accurately whether its own sub-tree is balanced. Complexity: Every node is visited once and all operations inside a visit are [math]O(1)[/math], giving overall [math]O(n)[/math] time and [math]O(h)[/math] auxiliary space (recursion depth), where [math]h \le n[/math] is the height of the tree.

Back to Chapter 3