## Algorithm

Problem Nmae: 110. Balanced Binary Tree

Given a binary tree, determine if it is

.

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]`.
• `-104 <= Node.val <= 104`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};

int maxDepth(struct TreeNode *root) {
if (root == NULL)
return 0;
int l = maxDepth(root->left);
int r = maxDepth(root->right);
if (l > r)
return l + 1;
else
return r + 1;
}

bool isBalanced(struct TreeNode *root) {
if (root == NULL)
return true;

int l = maxDepth(root->left);
int r = maxDepth(root->right);
int d = l - r;
if (d == 0 || d == 1 || d == -1) {
if (isBalanced(root->left) && isBalanced(root->right)) {
return true;
}
else return false;
}
else return false;
}

void printTreePreOrder(struct TreeNode *p) {
if (p != NULL) {
printf("%d", p->val);
printTreePreOrder(p->left);
printTreePreOrder(p->right);
}
else printf("#");
}

int main() {
struct TreeNode *t = (struct TreeNode *)calloc(7, sizeof(struct TreeNode));
struct TreeNode *p = t;
p->val = 1;

p->left = ++t;
t->val = 2;
p->left->left = ++t;
p->left->right = NULL;
t->val = 3;
p->left->left->left = ++t;
p->left->left->right = NULL;
t->val = 4;
t->left = t->right = NULL;

p->right = ++t;
t->val = 2;
p->right->left = NULL;
p->right->right = ++t;
t->val = 3;
p->right->right->left = NULL;
p->right->right->right = ++t;
t->val = 4;
t->left = t->right = NULL;

printTreePreOrder(p); printf("\n");

printf("%d\n", isBalanced(p)); /* should be false */
printf("%d\n", isBalanced(p->left)); /* should be false */
printf("%d\n", isBalanced(p->left->left)); /* should be true */
printf("%d\n", isBalanced(NULL)); /* should be true */

return 0;
}
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

cmd
true

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool isBalanced(TreeNode* root) {
bool res = true;
dfs(root, res);
return res;
}

int dfs(TreeNode* root, bool& res){
if(!root) return 0;
int l = dfs(root->left, res);
int r = dfs(root->right, res);
if(abs(l - r) > 1) res = false;
return max(l, r) + 1;
}
};
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

cmd
true

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
Map < TreeNode, Integer> map = new HashMap<>();
int leftHeight = getHeight(root.left, map);
int rightHeight = getHeight(root.right, map);
if (Math.abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}

private int getHeight(TreeNode root, Map < TreeNode, Integer> map) {
if (root == null) {
return 0;
}
if (map.containsKey(root)) {
return map.get(root);
}
int height = 1 + Math.max(getHeight(root.left, map), getHeight(root.right, map));
map.put(root, height);
return height;
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,2,3,3,null,null,4,4]

Output

cmd
false

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const isBalanced = function(root) {
return check(root) >= 0 ? true : false
};

const check = (root) => {
if(!root) return 1

const left = check(root.left)
if( left === -1 ) return -1

const right = check(root.right)
if( right === -1 ) return -1

if(Math.abs(left - right) > 1)return -1

return (1 + Math.max(left, right))
}
``````
Copy The Code &

Input

cmd
root = [1,2,2,3,3,null,null,4,4]

Output

cmd
false

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.computeHeight(root)!=-1
def computeHeight(self, node):
if not node: return 0
left_h=self.computeHeight(node.left)
right_h=self.computeHeight(node.right)
if left_h==-1 or right_h==-1 or abs(left_h-right_h)>1: return -1
return max(left_h,right_h)+1
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
true

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _110_BalancedBinaryTree
{
public bool IsBalanced(TreeNode root)
{
return GetHeight(root) != -1;
}

private int GetHeight(TreeNode current)
{
if (current == null) return 0;
var leftHeight = GetHeight(current.left);
if (leftHeight == -1) return -1;
var rightHeight = GetHeight(current.right);
if (rightHeight == -1) return -1;
if (Math.Abs(leftHeight - rightHeight) > 1) return -1;
return Math.Max(leftHeight, rightHeight) + 1;
}
}
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
true