# LeetCode 110. Balanced Binary Tree

## Description

https://leetcode.com/problems/balanced-binary-tree/

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.

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`

## Explanation

Check if left and right subtrees are balanced and whether their height difference is no more than 1.

## Java Solution

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return maxDepth(root) != null;
}

private Integer maxDepth(TreeNode root) {
if (root == null) {
return 0;
}

Integer leftDepth = maxDepth(root.left);
Integer rightDepth = maxDepth(root.right);

if (leftDepth == null || rightDepth == null) {
return null;
}

if (Math.abs(leftDepth - rightDepth) > 1) {
return null;
}

return Math.max(leftDepth, rightDepth) + 1;
}
}``````

## Python Solution

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def isBalanced(self, root: TreeNode) -> bool:

if not root:
return True

if not root.left and not root.right:
return True

left_height = self.height_helper(root.left)
right_height = self.height_helper(root.right)

return self.isBalanced(root.left) and self.isBalanced(root.right) and abs(left_height - right_height) <= 1

def height_helper(self, root):
if not root:
return 0

if not root.left and not root.right:
return 1

left = self.height_helper(root.left)

right = self.height_helper(root.right)

return max(left, right) + 1
``````
• Time Complexity: O(N)
• Space Complexity: O(N)