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 to Solve:

1. Recursive Depth Calculation: We'll use a recursive approach to calculate the height of each subtree. The height of a node is the maximum depth of its left and right subtrees, plus 1 (for the node itself).

2. Height Difference Check: During the recursive height calculation, we'll check the absolute difference between the heights of the left and right subtrees of each node. If this difference exceeds 1 at any point, the tree is unbalanced, and we can immediately return false.

3. Base Case: If a node is null, its height is -1 (this is a convention to handle empty subtrees correctly).

4. Return Value: The function will return true if the tree is balanced and false otherwise.

Explanation:

The solution leverages the post-order traversal pattern of recursion. We first recursively check the balance of the left and right subtrees. Only after confirming that both subtrees are balanced do we check if the current node's subtrees' heights differ by more than 1. If at any point the height difference is greater than 1, we know the tree is unbalanced, so we immediately return false. Otherwise, we continue the process recursively until all nodes are checked.

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -2; // -2 indicates an unbalanced tree
    }

    private int checkHeight(TreeNode node) {
        if (node == null) {
            return -1; // Height of an empty subtree is -1
        }

        int leftHeight = checkHeight(node.left);
        int rightHeight = checkHeight(node.right);

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

        return Math.max(leftHeight, rightHeight) + 1; // Height of this node
    }
}

Complexity:

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly 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 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.