Height-Balanced Binary Tree Solution

Problem Description

Given a binary tree, determine if it 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 1.

Brute Force Solution

The most straightforward approach is to check the balance condition for each node in the tree. This involves calculating the height of the left and right subtrees for every node and ensuring that the absolute difference between these heights is no more than 1. If this condition holds for every node, the tree is balanced.

Algorithm:

1. Define a helper function height(node) to calculate the height of a subtree rooted at node. The height of an empty tree is 0, and the height of a non-empty tree is 1 + max(height of left subtree, height of right subtree).
2. Define the main function isBalanced(root) to check if the tree is balanced. This function recursively checks the balance condition for each node.
3. For each node, calculate the heights of its left and right subtrees using the height function.
4. If the absolute difference between the heights of the left and right subtrees is greater than 1, the tree is not balanced. Return false.
5. Recursively check if the left and right subtrees are balanced.
6. If all nodes satisfy the balance condition, return true.

Code (Java):

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;

        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        if (Math.abs(leftHeight - rightHeight) > 1) return false;

        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }
}

Time Complexity: O(n^2), where n is the number of nodes in the tree. The height function is called for each node, and in the worst case, it traverses all nodes in the subtree.

Space Complexity: O(h), where h is the height of the tree. This is due to the recursive call stack. In the worst case (skewed tree), h = n, so the space complexity becomes O(n).

Optimal Solution

A more efficient approach is to calculate the height and check for balance in a single traversal. This can be done using a modified depth-first search (DFS).

Algorithm:

1. Define a recursive function getHeight(node) that returns the height of the subtree rooted at node. If the subtree is unbalanced, it returns -1.
2. If node is null, return 0 (base case).
3. Recursively calculate the height of the left and right subtrees.
4. If either the left or right subtree is unbalanced (height is -1), the current subtree is also unbalanced. Return -1.
5. Calculate the absolute difference between the heights of the left and right subtrees. If the difference is greater than 1, the current subtree is unbalanced. Return -1.
6. If the current subtree is balanced, return its height (1 + max(left height, right height)).
7. The main function isBalanced(root) calls getHeight(root) and returns true if the result is not -1, and false otherwise.

Code (Java):

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode node) {
        if (node == null) return 0;

        int leftHeight = getHeight(node.left);
        if (leftHeight == -1) return -1;

        int rightHeight = getHeight(node.right);
        if (rightHeight == -1) return -1;

        if (Math.abs(leftHeight - rightHeight) > 1) return -1;

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

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited only 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 (skewed tree), h = n, so the space complexity becomes O(n). In the best case (balanced tree), h = log n, so the space complexity is O(log n).

Edge Cases

• Empty tree: An empty tree is considered balanced.
• Single node tree: A tree with only one node is balanced.
• Skewed tree: A skewed tree (where all nodes are either left or right children) is the worst-case scenario for the brute-force approach.