110. Balanced Binary Tree¶
A binary tree is height-balanced if, for every node, the heights of its left and right subtrees differ by at most one. Checking balance and computing height are interdependent, so doing them separately would lead to repeated work. To avoid this, we use a bottom-up traversal where each recursive call returns two values:
- Whether the subtree is balanced
- The height of the subtree
For a given node, we first obtain the balance status and heights of its left and right subtrees. The current node is balanced if both subtrees are balanced and \(|leftHeight-rightHeight| \le 1\). The height of the current node is computed as \(1 + max(leftHeight, rightHeight)\).
By propagating both balance information and height upward together, we ensure that each node is processed only once. The final result is the balance status returned from the root.
Pseudocode
function helper(node):
if node is null:
return (true, 0)
(leftBalanced, leftHeight) = helper(node.left)
(rightBalanced, rightHeight) = helper(node.right)
balanced = leftBalanced AND rightBalanced AND abs(leftHeight - rightHeight) ≤ 1
height = 1 + max(leftHeight, rightHeight)
return (balanced, height)
Runtime Complexity
Time: \(O(n)\)
Space: \(O(h)\)
class Solution:
def _helper(self, node):
if not node:
return True, 0
lb, lh = self._helper(node.left)
rb, rh = self._helper(node.right)
b = abs(lh-rh) <= 1 and lb and rb
h = 1+max(lh, rh)
return b, h
def isBalanced(self, root: Optional[TreeNode]) -> bool:
balanced, _ = self._helper(root)
return balanced
func isBalanced(root *TreeNode) bool {
var helper func(node *TreeNode) (bool, int)
helper = func(node *TreeNode) (bool, int) {
if node == nil {
return true, 0
}
lb, lh := helper(node.Left)
rb, rh := helper(node.Right)
b := math.Abs(float64(lh)-float64(rh)) <= 1 && lb && rb
h := 1 + max(lh, rh)
return b, h
}
balanced, _ := helper(root)
return balanced
}