LeetCode 110: Balanced Binary Tree — Step-by-Step Visual Trace

#leetcode #python #algorithms #datastructures

Easy — Binary Tree | Recursion | Tree Traversal | Depth-First Search

The Problem

Determine if a binary tree is height-balanced, where for every node the heights of its left and right subtrees differ by at most one.

Approach

Use a recursive helper function to calculate height while simultaneously checking balance conditions. If any subtree is unbalanced, propagate infinity upward to indicate imbalance, otherwise return the actual height.

Time: O(n) · Space: O(h)

Code

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def height(node):
            if not node:
                return 0
            left_height = height(node.left)
            right_height = height(node.right)
            if abs(left_height - right_height) > 1:
                return float("inf")  # Indicate imbalance
            return max(left_height, right_height) + 1

        return height(root) != float("inf")