## Similar Problems

Similar Problems not available

# Balanced Binary Tree - Leetcode Solution

LeetCode: Balanced Binary Tree Leetcode Solution

Difficulty: Easy

Topics: tree binary-tree depth-first-search

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.

## Balanced Binary Tree Solution Code

`1`