110. Balanced Binary Tree

Description

The problem is to determine whether a given binary tree is height-balanced. A binary tree is considered height-balanced if, for every node in the tree, the height difference between the left and right subtrees is at most 1.

Intuition

A height-balanced tree ensures that the tree is as compact as possible, which makes operations like search, insert, and delete more efficient. The key observation is that a tree is balanced if and only if the left and right subtrees of every node are balanced and the difference in their heights is no more than 1.

Approach

1. Post-order Traversal: - Use a recursive function to perform a post-order traversal of the tree. This means that for each node, the function will first calculate the height of its left and right subtrees before checking if the current node is balanced.
2. Height Calculation: - For each node, calculate the height of the left and right subtrees. The height of a node is the maximum of the heights of its left and right subtrees, plus one.
3. Balance Check: - If the absolute difference in heights between the left and right subtrees is greater than 1, mark the tree as unbalanced.
4. Return the Result: - After the entire tree has been traversed, return the result indicating whether the tree is balanced or not.

Complexity

Time Complexity:

The time complexity is (O(n)), where n is the number of nodes in the tree. This is because each node is visited once during the traversal.

Space Complexity:

The space complexity is (O(h)), where h is the height of the tree. This is due to the recursion stack, which at most will be as deep as the height of the tree.

Code

C++

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        bool isBal = true;

        std::function maxDepth = [&](TreeNode* node) -> int {
            if (!node) return 0;
            int leftSub = maxDepth(node->left);
            int rightSub = maxDepth(node->right);
            if (std::abs(leftSub - rightSub) > 1) {
                isBal = false;
            }
            return std::max(leftSub, rightSub) + 1;
        };

        maxDepth(root);
        return isBal;
    }
};

Python

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        self.isBal = True

        def maxDepth(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            leftSub = maxDepth(node.left)
            rightSub = maxDepth(node.right)
            if abs(leftSub - rightSub) > 1:
                self.isBal = False
            return max(leftSub, rightSub) + 1

        maxDepth(root)
        return self.isBal

Java

class Solution {
    private boolean isBal = true;

    public boolean isBalanced(TreeNode root) {
        maxDepth(root);
        return isBal;
    }

    private int maxDepth(TreeNode node) {
        if (node == null) return 0;
        int leftSub = maxDepth(node.left);
        int rightSub = maxDepth(node.right);
        if (Math.abs(leftSub - rightSub) > 1) {
            isBal = false;
        }
        return Math.max(leftSub, rightSub) + 1;
    }
}

JavaScript

var isBalanced = function (root) {

    let isBal = true

    var maxDepth = function (node) {
        if (!node) return 0
        let leftSub = maxDepth(node.left)
        let rightSub = maxDepth(node.right)
        if (Math.abs(leftSub - rightSub) > 1) {
            isBal = false
        }
        return Math.max(leftSub, rightSub) + 1
    }
    maxDepth(root)
    return isBal
};