Return true if the tree is height-balanced: for every node, the heights of its
left and right subtrees differ by at most 1.
isTreeBalanced(root)
Input format: level-order with x for missing children. An empty tree is balanced.
3 9 20 x x 15 7 // → true
1 2 x 3 x x x 4 // → false
(empty) // → true
A balanced tree's definition is recursive: every node, not just the root, must have left and right subtree heights differing by at most one. The property has to hold everywhere, all the way down.
A direct translation: compute a subtree's height, then at every node compare its children's heights. But computing height means visiting every node in that subtree, and you'd redo it from scratch at every node in the tree. A node near the root gets its height recomputed by every ancestor's balance check, and near-root nodes have O(n) descendants — O(n) work per node times O(n) nodes gives O(n²).
Height and balance aren't independent — you need a subtree's height to check its balance anyway, and a subtree's balance to matter to its parent. So do both at once: one recursive helper that computes height while simultaneously detecting an imbalance anywhere within it.
The helper works post-order: recurse into the left child for its height (or a failure signal), then the right. If either already failed, propagate that failure immediately — nothing above can un-break it. If both succeeded, compare their heights: differing by more than one means this node is the imbalance point — report failure. Otherwise this node is fine, and its height is one more than the taller child — report that upward. A missing node has height 0, trivially balanced. The tree is balanced exactly when the root's call doesn't fail.
Each node computes its own height once, using its children's already-computed heights — constant work beyond the two recursive calls. That collapses the repeated recomputation entirely — O(n) time, O(h) space for the recursion stack.
def is_tree_balanced(root):
def height(node):
if node is None:
return 0
l = height(node.left)
if l == -1:
return -1
r = height(node.right)
if r == -1:
return -1
if abs(l - r) > 1:
return -1
return max(l, r) + 1
return height(root) != -1
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.