# 110. Balanced Binary Tree

checkout the problem description here.

SOLUTION

*Recursive approaches*

Approach 1:

*Naive approach*

Iterate through the tree and find left height and right height of the subtree(another helper function that calculates the height is called) and check if balanced. Check for its left and right node and so on.

A kind of top down approach.

check(node):

if root

return true left_height = height_find(node.left)+1

right_height =height_find(node.right)+1 if abs(left_height -right_height) >1

return false left = check(node.left)

right = check(node.right)

if left ==false or right == false

return false

return true

**Time : O(n²)**

**Space : O(n) at max if skew tree**

Approach 2:

*The more optimized way*

Recursively iterate and find the height of left and right subtree and if the height differ by more than 1 , return a -1.Which is a flag used to indicate that the tree is unbalanced.

A kind of bottom up approach.

class Solution:

def isBalanced(self, root: Optional[TreeNode]) -> bool:

if self.rec(root) ==-1:

return False

return True

def rec(self,root):

if not root:

return 0

left = self.rec(root.left)

right=self.rec(root.right)

if left==-1 or right == -1 or abs(right-left)>1 :

return -1

return 1 + max(left,right)

**Time : O(n)**

**Space : O(n) at max if skew tree**