[[Binary trees and Binary search trees]]

Problem

Given a binary tree, determine if it is height-balanced.

Brainstorming

what is a balanced tree? its a tree where the height of its left child and right child is at most 1 . When you are at a node you would need the left tree height and the right tree height , we can check the difference between them if its more than 1 then we can return False. Once the traversal ends and we don’t short the traversal even once then we can safely return True.

1. initialise a function get_height(node) which takes in a node
2. for each node we pass get_height(node.left) and get_height(node.right) for its left and right nodes (post order traversal)
3. Once we have left_height and the right_height then we can subtract and check the difference if the difference abs(left_height - right_height) is > 1 then we can return false
4. If at the end of the recursive helper we don’t exit early then the main function will return by default True

This brute force algo will work well but the problem is it will do a lot of repeat calculations for subtrees as we will go down in the traversal. This is a bit inefficient . But we are doing it because the node at this point does not know if the left tree or the right tree is balanced or not we only get the height, so we end up calculating the subtree height multiple times.

The best way to solve it is if instead of just returning the height we also return a flag that tells if below the current level tree is balanced or not. It solves 2 problems . One we don’t need to calculate the subtree height again and again since the flag will tell us if the tree is balanced or not. If its balanced then we can calculate at the current node the height and decide only for the current node level. If they are not balanced then anyway we don’t have to worry about calculating the heights at all and just return false ,

Below is the updated algorithm

1. initialise the recursive helper with a new parameter get_height(node) that returns is_balanced and height
2. the base case would be if we have hit an empty tree then the returning value would be False and the height would be -1
3. now we will first ask the left and the right subtrees for the status and height is_left_balanced, left_height = get_height(node.left) and is_right_balanced, right_height = get_height(node.right)
4. check for the flags is_left_balanced and is_right_balanced if they are false then there is no need to calculate the height at the current level and just return False, -1
5. if they both are balanced then we will caculate the height difference between left_height and right_height if its greater than 1 then we will return False and -1
6. if its less than equal to 1 then we return True and max(left_height, right_height) + 1

class TreeNode: 
	def __init__(self, val=0, left=None, right=None): 
		self.val = val 
		self.left = left 
		self.right = right
	

def is_height_balanced(node:TreeNode):
	if node is None:
		return True, -1
	
	is_left_balanced, left_height = is_height_balanced(node.left)
	
	if not is_left_balanced:
		return False , -1
		
	is_right_balanced, right_height = is_height_balanced(node.right)
	
	if not is_right_balanced:
		return False , -1	
	

	
	height_diff = abs(left_height - right_height)
	
	if height_diff > 1:
		return False , -1
	else:
		return True , max(left_height, right_height) + 1 
		

Key take aways

an empty tree is by definition balanced hence it will return True