**Solution**

**Balanced Binary Tree** https://leetcode.com/problems/balanced-binary-tree/?tab=Description

**Brute Force**

- Traverse and find height at each node. Test if it is balanced and subsequently recursively call on root.left and root.right. What is time complexity? How many times is node "touched" or called? Answer is at max "h" times (i.e. path from node to root), where h is the height of the tree. Visualize it. Now
**if the tree is balanced, we have O(NLgN), otherwise worst case is O(N^2). The accurate complexity is O(Nh) and space complexity is O(h).**

**Post-Order Algorithm**

- Optimization is using post order traversal - test height and balance in one call and propogate it upwards. In Python, we can return two variables. In other languages, we can return an error code in height. Complexity O(N) and space is O(h).

```
class Solution(object):
def helper(self, root):
if root == None:
return 0, True
hl, lb = self.helper(root.left)
hr, rb = self.helper(root.right)
if lb and rb and abs(hl-hr) <= 1:
return max(hl,hr) + 1, True
else:
return -1, False
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
h, is_b = self.helper(root)
return is_b
```