LeetCode Solutions Blog

Balanced Binary Tree

Number: 110

Difficulty: Easy

Paid? No

Problem Description

Determine if a given binary tree is height-balanced. A binary tree is balanced if the depth of its two subtrees never differs by more than one.

Key Insights

Use a bottom-up DFS (Depth-First Search) traversal to compute the height of each subtree.
If any subtree is found unbalanced, propagate an error indicator (e.g., -1) upward, allowing early termination.
An empty tree is considered balanced.
The key check is to ensure that for each node, the absolute difference between the heights of its left and right subtrees is no more than 1.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes in the tree, since we visit each node once. Space Complexity: O(h) where h is the height of the tree, which corresponds to the recursion stack (O(n) in the worst-case of a skewed tree).

Solution

The solution uses a recursive DFS approach. A helper function recursively computes the height of a subtree. If a subtree is found to be unbalanced (the height difference between its left and right subtrees exceeds 1), the helper returns a special value (e.g., -1) to indicate that the subtree is unbalanced. This value is then propagated up the recursion to terminate further unnecessary computations. The main function checks the result of the helper function and returns true if the tree is balanced (i.e., the helper did not return -1) and false otherwise.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # Helper function to return the height of the subtree or -1 if unbalanced.
        def checkHeight(node: TreeNode) -> int:
            # An empty tree has height 0 and is balanced.
            if not node:
                return 0
            
            # Recursively get the height of the left subtree.
            leftHeight = checkHeight(node.left)
            # If left subtree is unbalanced, return -1.
            if leftHeight == -1:
                return -1
            
            # Recursively get the height of the right subtree.
            rightHeight = checkHeight(node.right)
            # If right subtree is unbalanced, return -1.
            if rightHeight == -1:
                return -1
            
            # If the current node's subtrees differ in height by more than 1, it's unbalanced.
            if abs(leftHeight - rightHeight) > 1:
                return -1
            
            # Return the height of the current node.
            return max(leftHeight, rightHeight) + 1
        
        # The tree is balanced if checkHeight does not return -1.
        return checkHeight(root) != -1