110. Balanced Binary Tree – Leetcode Solutions

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
Example 3:

Input: root = []
Output: true

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # Helper function to determine the height of the tree
        # and check if it is balanced at the same time.
        def check_balance(node):
            # If node is None, it is balanced and height is 0.
            if not node:
                return 0, True
            
            # Recursively check the left subtree.
            left_height, left_balanced = check_balance(node.left)
            # Recursively check the right subtree.
            right_height, right_balanced = check_balance(node.right)
            
            # Current node's height.
            current_height = max(left_height, right_height) + 1
            
            # Check if the current node is balanced.
            current_balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
            
            return current_height, current_balanced
        
        # Call the helper function starting from the root.
        _, balanced = check_balance(root)
        
        return balanced

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    /**
     * Helper function to determine the height of the tree
     * and check if it is balanced at the same time.
     * @param {TreeNode} node
     * @return {Array} [height, balanced]
     */
    function checkBalance(node) {
        // If node is null, it is balanced and height is 0
        if (node === null) {
            return [0, true];
        }
        
        // Recursively check the left subtree
        const [leftHeight, leftBalanced] = checkBalance(node.left);
        // Recursively check the right subtree
        const [rightHeight, rightBalanced] = checkBalance(node.right);
        
        // Current node's height
        const currentHeight = Math.max(leftHeight, rightHeight) + 1;
        
        // Check if the current node is balanced
        const currentBalanced = leftBalanced && rightBalanced && Math.abs(leftHeight - rightHeight) <= 1;
        
        return [currentHeight, currentBalanced];
    }
    
    // Call the helper function starting from the root
    const [, balanced] = checkBalance(root);
    
    return balanced;
};

class Solution {
    /**
     * Determine if a binary tree is height-balanced.
     * @param root The root node of the binary tree.
     * @return True if the tree is balanced, false otherwise.
     */
    public boolean isBalanced(TreeNode root) {
        // Call the helper function to check the balance and get the height
        return checkBalance(root)[1] == 1;
    }

    /**
     * Helper function to check the balance of the tree.
     * @param node The current node being checked.
     * @return An array where the first element is the height of the tree
     *         and the second element is 1 if the tree is balanced, 0 otherwise.
     */
    private int[] checkBalance(TreeNode node) {
        // If the node is null, it's balanced and height is 0
        if (node == null) {
            return new int[]{0, 1};
        }

        // Recursively check the left subtree
        int[] left = checkBalance(node.left);
        // Recursively check the right subtree
        int[] right = checkBalance(node.right);

        // Calculate the current height
        int height = Math.max(left[0], right[0]) + 1;

        // Check if the current node is balanced
        boolean balanced = left[1] == 1 && right[1] == 1 && Math.abs(left[0] - right[0]) <= 1;

        // Return the height and balance status
        return new int[]{height, balanced ? 1 : 0};
    }
}

public class Solution {
    /**
     * Determine if a binary tree is height-balanced.
     * @param root The root node of the binary tree.
     * @return True if the tree is balanced, false otherwise.
     */
    public bool IsBalanced(TreeNode root) {
        // Call the helper function to check the balance and get the height
        return CheckBalance(root).Item2;
    }

    /**
     * Helper function to check the balance of the tree.
     * @param node The current node being checked.
     * @return A tuple where the first element is the height of the tree
     *         and the second element is true if the tree is balanced, false otherwise.
     */
    private (int, bool) CheckBalance(TreeNode node) {
        // If the node is null, it's balanced and height is 0
        if (node == null) {
            return (0, true);
        }

        // Recursively check the left subtree
        var left = CheckBalance(node.left);
        // Recursively check the right subtree
        var right = CheckBalance(node.right);

        // Calculate the current height
        int height = Math.Max(left.Item1, right.Item1) + 1;

        // Check if the current node is balanced
        bool balanced = left.Item2 && right.Item2 && Math.Abs(left.Item1 - right.Item1) <= 1;

        // Return the height and balance status
        return (height, balanced);
    }
}