Balanced Binary Tree - Leetcode Solution

The Balanced Binary Tree problem on LeetCode can be found at https://leetcode.com/problems/balanced-binary-tree/.

The problem statement is as follows: 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.

To solve this problem, we need to recursively check the height of the left and right subtrees of each node and compare them. If the difference between the heights is greater than 1, then the tree is not height-balanced.

We will implement a recursive solution to check the height of the tree and compare the heights of the left and right subtrees.

First, we will define a helper function to calculate the height of a given node:

int height(TreeNode* node) {
    if (!node) {
        return 0;
    }
    return 1 + max(height(node->left), height(node->right));
}

The height function takes a node as input and recursively calculates the height of the subtree rooted at that node. If the node is NULL, the function returns 0. Otherwise, it returns 1 plus the maximum height of the left and right subtrees.

Next, we will define the main function isBalanced which takes the root of the binary tree as input:

bool isBalanced(TreeNode* root) {
    if (!root) {
        return true;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if (abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    return isBalanced(root->left) && isBalanced(root->right);
}

The isBalanced function first checks if the root is NULL. If it is NULL, the function returns true because an empty tree is always height-balanced.

If the root is not NULL, we calculate the height of the left and right subtrees using the height function. We then check if the absolute difference between the heights is greater than 1. If it is, the function returns false because the tree is not height-balanced.

If the difference between the heights is less than or equal to 1, we recursively call isBalanced on the left and right subtrees. If both subtrees are height-balanced, the function returns true. Otherwise, if either subtree is not height-balanced, the function returns false.

The time complexity of this solution is O(n^2) in the worst case because we may need to calculate the height of each node in the binary tree, and each height calculation takes O(n) time in the worst case. The space complexity is O(n) because we use recursion to traverse the binary tree and store the maximum height of each subtree on the call stack.

However, we can optimize the time complexity to O(n) by calculating the height of each node only once. We can do this by modifying the height function to check if the subtree rooted at a node is height-balanced and return the height of the subtree at the same time. This avoids redundant calculations of the subtree height.

Here is the optimized height function:

int height(TreeNode* node, bool& balanced) {
    if (!node) {
        return 0;
    }
    int leftHeight = height(node->left, balanced);
    int rightHeight = height(node->right, balanced);
    if (abs(leftHeight - rightHeight) > 1) {
        balanced = false;
    }
    return 1 + max(leftHeight, rightHeight);
}

We add a boolean parameter balanced to the height function to indicate if the subtree rooted at a node is height-balanced. If the difference between the heights of the left and right subtrees is greater than 1, we set balanced to false.

Here is the modified isBalanced function using the optimized height function:

bool isBalanced(TreeNode* root) {
    bool balanced = true;
    height(root, balanced);
    return balanced;
}

The isBalanced function initializes balanced to true and calls the height function on the root. The function then returns the value of balanced.

With the optimized height function, the time complexity of this solution is O(n) in the worst case, and the space complexity is O(n) due to the recursion.

1