### Problem Statement#

Given a binary tree, determine if it is height-balanced

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

#### Example 1:#

``````    3
9       20
15      7

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

#### Example 2:#

``````
1
2       2
3       3
4       4

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
``````

#### Example 3:#

``````Input: root = []
Output: true
``````

### Key Insights#

A binary tree is considered height balanced if the height differences between the left and right subtrees are less than or equal to one.

To solve this problem, we can write a recursive function that checks if the height difference between a node’s left and right subtrees is <= `1`. If the check passes, the function can then check the left and right subtrees recursively.

### Recursive 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

from collections import deque
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
# A null node is considered balanced
return True
elif abs(self.height(root.left) - self.height(root.right)) > 1:
# Return False if the height difference between the left and right
# subtrees is greater than one.
return False
else:
# Call the function recursively on the left and right subtrees
# to check the height difference at each node.
return self.isBalanced(root.left) and self.isBalanced(root.right)

def height(self, node: Optional[TreeNode]) -> int:
if not node:
return 0
else:
# For each node, find the height of the
# left and right subtrees.
left  = self.height(node.left)
right = self.height(node.right)
# By adding 1 at each level, we can
# count each node on the longest path
# to give us the height of the tree
# whose root is 'node'.
return max(left, right) + 1
``````

### Iterative 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

from collections import deque
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
# A null node is considered balanced
return True
elif abs(self.height(root.left) - self.height(root.right)) > 1:
# Return False if the height difference between the left and right
# subtrees is greater than one.
return False
else:
# Call the function recursively on the left and right subtrees
# to check the height difference at each node.
return self.isBalanced(root.left) and self.isBalanced(root.right)

def height(self, node: Optional[TreeNode]) -> int:
if not node:
return 0

queue = deque([(node, 0)])
ans = 0

while queue:
# Iteratively traverse through the tree and
# update the ans with the max of the left and right
# subtrees (at each node)
node, height = queue.popleft()
height += 1
ans = max(ans, height)

if node.left:
queue.append((node.left, height))

if node.right:
queue.append((node.right, height))

return ans

``````

Leetcode 110 Balanced Binary Tree