> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/trees/binary ]
> [project group:: Neetcode 150]
> [difficulty:: done]
> [status:: in progress]
> [link:: https://leetcode.com/problems/balanced-binary-tree/]
> [up:: [[Leetcode MOC]]]
## Problem
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
**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]`.
- `-10e4 <= Node.val <= 10e4`
## Solution
### Mine
#### Python
```python
# 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: Optional[TreeNode]) -> bool:
if not root:
return True
def _get_depth(root: TreeNode) -> Tuple[bool, int]:
if not root:
return True, 0
left, right = _get_depth(root.left), _get_depth(root.right)
balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
return balanced, 1 + max(left[1], right[1])
return _get_depth(root)[0]
```
#### Rust
### LC's
## Things I Learned
### Neetcode
My initial approach is $O(n)^2$. Instead of asking if tree is balanced from root node, start with base case (deepest node) before making comparisons, which allows you to only need to visit each node once, resulting in $O(n)$.
Once we determined leaf subtrees (of 0) are balanced, then we return
## Scratchpad
One approach could be to use depth traversal and get the deepest and shallowest nodes. At each final depth, compare deepest, shallowest, and current.