  # LeetCode - Balanced Binary Tree

## Problem statement

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.``

Problem statement taken from: https://leetcode.com/problems/balanced-binary-tree

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
``````

Constraints:

``````- The number of nodes in the tree is in the range [0, 5000]
- -10^4 <= Node.val <= 10^4
``````

### Explanation

#### Brute force approach

The brute force approach to verify if the tree is balanced or not is to get the height of left and right sub-trees. If the difference is not more than 1, we return true else false.

A C++ snippet of the above approach looks as below:

``````int height(node* node) {
if (node == NULL)
return 0;

return 1 + max(height(node->left), height(node->right));
}

bool isBalanced(node* root) {
int leftHeight, rightHeight;

if (root == NULL)
return 1;

leftHeight = height(root->left);
rightHeight = height(root->right);

if (abs(leftHeight - rightHeight) <= 1 && isBalanced(root->left) && isBalanced(root->right))
return 1;

return 0;
}``````

The time complexity of the above approach is O(N^2).

#### Optimized solution

If we observe the approach closely, we can calculate the difference in the left and right sub-trees in the height recursion function. If at any point of time the difference between left and right subtree is greater than 1 we return false.

Let's check the algorithm first.

``````// isBalanced function
1. - if root == nullptr
- return true

2. - return height(root) != -1

// height function
3. - if root == nullptr
- return 0

4. - set leftHeight = height(root->left)
5. - set rightHeight = height(root->right)

6. - if leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1
- return -1

7. - return 1 + max(leftHeight, rightHeight)
``````

In the isBalanced function, we first check if the tree is empty or not. If it's empty, we return true. If not, we pass the root to the height function.

Inside the height function, we check if the root is empty. We return 0 for the empty element.

At steps 4 and 5, we recursively call left and right sub-trees. In step 6, we check if the leftHeight or rightHeight is -1 or the absolute difference between left and right height is greater than 1. If the difference is above 1, we are returning -1. The flow fallback to step 2 and verify if -1 != -1. That's false and indicates the tree is not balanced. Else we return at step 7, 1 + max(leftHeight, rightHeight)

#### C++ solution

``````class Solution {
public:
int height(TreeNode* root) {
if(root == nullptr) {
return 0;
}

int leftHeight = height(root->left);
int rightHeight = height(root->right);

if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
return -1;
}

return 1 + max(leftHeight, rightHeight);
}

bool isBalanced(TreeNode* root) {
if(root == nullptr) {
return true;
}

return height(root) != -1;
}
};``````

#### Golang solution

``````func maximum(a, b int) int {
if a > b {
return a
} else {
return b
}
}

func height(root *TreeNode) int {
if root == nil {
return 0;
}

leftHeight := height(root.Left)
rightHeight := height(root.Right)

if leftHeight == -1 || rightHeight == -1 || int(math.Abs(float64(leftHeight - rightHeight))) > 1 {
return -1
}

return 1 + maximum(leftHeight, rightHeight)
}

func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}

return height(root) != -1
}``````

#### Javascript solution

``````var height = function(root) {
if(root === null) {
return 0;
}

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

if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}

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

var isBalanced = function(root) {
if(root === null) {
return true;
}

return height(root) != -1;
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

``````Input: root = [3, 9, 20, null, null, 15, 7]

root
|
[3, 9, 20, null, null, 15, 7]

// In isBalanced function
Step 1: if root == nullptr
false

Step 2: return height(root) != -1

// In height function

root
|
[3, 9, 20, null, null, 15, 7]

Step 3: if root == nullptr
false

Step 4: leftHeight = height(root->left)
root->left points to 9

root
|
[3, 9, 20, null, null, 15, 7]

Step 5: if root == nullptr
false

Step 6: leftHeight = height(root->left)
root->left points to null
So we get back here with value as 0 and it calls the next step.

rightHeight = height(root->right)
root->right points to null
So we get back here with a value of 0, and it calls the next step.

leftHeight = 0
rightHeight = 0
abs(0 - 0) > 1
false

if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
false

return 1 + max(leftHeight, rightHeight)
1 + max(0, 0)
1

Step 7: We fallback to Step 4 and execute the next line
rightHeight = height(root->right)
root->right points to 20

root
|
[3, 9, 20, null, null, 15, 7]

Step 9: if root == nullptr
false

Step 10: leftHeight = height(root->left)
root->left points to 15

root
|
[3, 9, 20, null, null, 15, 7]

Step 11: if root == nullptr
false

Step 12: leftHeight = height(root->left)
root->left points to null
So we get back here with value as 0 and it calls the next step.

rightHeight = height(root->right)
root->right points to null
So we get back here with a value of 0, and it calls the next step.

leftHeight = 0
rightHeight = 0
abs(0 - 0) > 1
false

if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
false

return 1 + max(leftHeight, rightHeight)
1 + max(0, 0)
1

Step 13: We fallback to step 10 and execute next line
rightHeight = height(root->right)
root->right points to 7

root
|
[3, 9, 20, null, null, 15, 7]

Step 14: if root == nullptr
false

Step 15: leftHeight = height(root->left)
root->left points to null
So we get back here with value as 0 and it calls the next step.

rightHeight = height(root->right)
root->right points to null
So we get back here with a value of 0, and it calls the next step.

leftHeight = 0
rightHeight = 0
abs(0 - 0) > 1
false

if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
false

return 1 + max(leftHeight, rightHeight)
1 + max(0, 0)
1

Step 16: We fallback to Step 7 and execute next lines
leftHeight = 1
rightHeight = 1
abs(1 - 1) > 1
false

if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
false

return 1 + max(leftHeight, rightHeight)
1 + max(1, 1)
2

Step 17: We fallback to Step 2 and execute next lines
leftHeight = 1
rightHeight = 2
abs(1 - 2) > 1
false

if(leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
false

return 1 + max(leftHeight, rightHeight)
1 + max(1, 2)
3

Step 18: We return back to isBalanced function and execute the last return part
return height(root) != -1
3 != -1
true

So we return the answer as true.
``````