Problem Statement

Given a binary tree, determine if it is height-balanced

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

    3
9       20
    15      7

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:


            1
        2       2
    3       3
4       4

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Key Insights

A binary tree is considered height balanced if the height differences between the left and right subtrees are less than or equal to one.

To solve this problem, we can write a recursive function that checks if the height difference between a node’s left and right subtrees is <= 1. If the check passes, the function can then check the left and right subtrees recursively.

Recursive Solution

# 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

from collections import deque
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            # A null node is considered balanced
            return True
        elif abs(self.height(root.left) - self.height(root.right)) > 1:
            # Return False if the height difference between the left and right
            # subtrees is greater than one.
            return False
        else:
            # Call the function recursively on the left and right subtrees
            # to check the height difference at each node.
            return self.isBalanced(root.left) and self.isBalanced(root.right)

    def height(self, node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        else:
            # For each node, find the height of the 
            # left and right subtrees.
            left  = self.height(node.left)
            right = self.height(node.right)
            # By adding 1 at each level, we can 
            # count each node on the longest path
            # to give us the height of the tree
            # whose root is 'node'.
            return max(left, right) + 1

Iterative Solution

# 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

from collections import deque
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            # A null node is considered balanced
            return True
        elif abs(self.height(root.left) - self.height(root.right)) > 1:
            # Return False if the height difference between the left and right
            # subtrees is greater than one.
            return False
        else:
            # Call the function recursively on the left and right subtrees
            # to check the height difference at each node.
            return self.isBalanced(root.left) and self.isBalanced(root.right)
    
    def height(self, node: Optional[TreeNode]) -> int:
        if not node:
            return 0

        queue = deque([(node, 0)])
        ans = 0

        while queue:
            # Iteratively traverse through the tree and 
            # update the ans with the max of the left and right
            # subtrees (at each node)
            node, height = queue.popleft()
            height += 1
            ans = max(ans, height)

            if node.left:
                queue.append((node.left, height))
            
            if node.right:
                queue.append((node.right, height))
        
        return ans

Leetcode 110 Balanced Binary Tree