110. Balanced Binary Tree

checkout the problem description here.

Balanced Binary Tree - LeetCode

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