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