Balanced Binary Tree easy

Problem Statement

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

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

Example 2:

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

Steps:

1. Depth Calculation: We need a function to calculate the depth (height) of a binary tree. This function will recursively traverse the tree.

2. Balanced Check: A recursive helper function checks if a subtree is balanced. It does this by:

   • Recursively calculating the depth of the left and right subtrees.
   • Checking if the absolute difference between the depths is greater than 1. If it is, the subtree is unbalanced, and we immediately return False.
   • If the subtrees are balanced, we return the maximum depth of the two subtrees + 1 (to include the current node).

3. Main Function: The main function simply calls the helper function on the root node.

Explanation:

The key idea is to avoid redundant calculations. We calculate the height of subtrees only once and use that information to check the balance condition. If a subtree is unbalanced, we immediately return False without further exploration, making the algorithm efficient. A simple recursive depth check alone wouldn't be efficient, as it would repeatedly recalculate heights for the same nodes.

Code:

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:
        def check_height(node):
            if not node:
                return 0
            
            left_height = check_height(node.left)
            if left_height == -1:
                return -1
            
            right_height = check_height(node.right)
            if right_height == -1:
                return -1
            
            if abs(left_height - right_height) > 1:
                return -1
            
            return max(left_height, right_height) + 1

        return check_height(root) != -1

Complexity:

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node at most once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N, resulting in O(N) space complexity. In the best case (a balanced tree), H is log₂(N), resulting in O(log N) space complexity.