Solution Explanation: Balanced Binary Tree

This problem asks whether a given binary tree is height-balanced. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Approach: Bottom-Up Recursion

The most efficient approach is using a bottom-up recursive method. This approach avoids redundant calculations by calculating the height of each subtree only once.

The core idea is to define a helper function height(node) that returns the height of a subtree rooted at node. This function has the following logic:

1. Base Case: If node is null (empty subtree), the height is 0.
2. Recursive Step: Recursively calculate the heights of the left and right subtrees (left_height, right_height).
3. Balance Check: If either left_height or right_height is -1 (indicating an imbalance in a subtree), or if the absolute difference between left_height and right_height is greater than 1, then the current subtree is unbalanced, so return -1.
4. Height Calculation: If the subtree is balanced, return max(left_height, right_height) + 1.

The main function isBalanced(root) simply calls the height() function on the root node. If height(root) returns a non-negative value, the tree is balanced; otherwise, it's not.

Time and Space Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once during the traversal.
• 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 N, but for a balanced tree, H is log₂(N). Therefore, the space complexity is O(log N) for a balanced tree and O(N) for a skewed tree.

Code Implementation (Python)

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

The code in other languages (Java, C++, Go, TypeScript, Rust, JavaScript) follows the same logic, adapting the syntax and data structures to the specific language. The core recursive height function remains the same in its structure and purpose.