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 left and right subtrees of every node differ in height by no 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. Helper Function: Create a helper function getHeight that recursively calculates the height of a subtree. If a subtree is null, its height is -1 (this simplifies the height difference calculation).

2. Height Calculation: The getHeight function will recursively traverse the left and right subtrees, calculating their heights. If either subtree is not balanced (meaning the absolute difference in their heights is > 1), the function immediately returns -2 (a value to signify an unbalanced tree).

3. Balanced Check: If the subtree is balanced, the function returns the maximum height between left and right subtrees + 1.

4. Main Function: The main function isBalanced calls getHeight on the root node. If getHeight returns -2, the tree is unbalanced, and the function returns false. Otherwise, the tree is balanced, and the function returns true.

Explanation

The core idea is to use a post-order traversal (or a recursive approach that implicitly does a post-order traversal). We calculate the height of each subtree before checking if it's balanced. This allows for efficient early termination: if we detect an imbalance in a subtree, we don't need to continue recursively processing its children, as we know the entire tree will be unbalanced. Using a return value of -2 to signal an unbalanced subtree efficiently propagates this information up the tree.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function isBalanced(root: TreeNode | null): boolean {
    return getHeight(root) !== -2;
};


function getHeight(root: TreeNode | null): number {
    if (root === null) {
        return -1;
    }

    const leftHeight = getHeight(root.left);
    const rightHeight = getHeight(root.right);

    if (leftHeight === -2 || rightHeight === -2 || Math.abs(leftHeight - rightHeight) > 1) {
        return -2; // Unbalanced
    }

    return Math.max(leftHeight, rightHeight) + 1;
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we visit each node 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 could be N, but for balanced trees, H is log N.