Lesson 3 � Intermediate

Height, Diameter, Balanced Tree

Tree ke size ke baare mein kuch important measurements hain � height (kitna lamba hai), diameter (sabse lambi path kya hai), aur balanced hai ya nahi. Ye concepts interview mein bahut aate hain aur recursion ke beautiful examples hain.

? 20 min✓ Intermediate✓ Binary Tree basics, Recursion

Height of Binary Tree

WHAT

Tree ki height = root se sabse lambi path mein kitne edges hain. Empty tree ki height 0 hoti hai. Single node tree ki height 1 hoti hai (ya 0 depending on convention � hum 0-based use karte hain: edges count).

WHEN

Tree balanced hai ya nahi check karne ke liye, tree ka structure samajhne ke liye, aur bahut si tree problems mein height ka use hota hai. Height O(n) mein calculate hoti hai.

WHERE

Balanced BST (AVL trees) mein height se balancing factor nikalta hai. Compiler design mein expression trees ki height se evaluation order decide hota hai.

def height(node):
 if node is None:
 return 0
 return 1 + max(height(node.left), height(node.right))

# Example:
# 1
# / \
# 2 3
# /
# 4

# height(4) = 1 + max(0, 0) = 1
# height(2) = 1 + max(1, 0) = 2
# height(3) = 1 + max(0, 0) = 1
# height(1) = 1 + max(2, 1) = 3

# Height = 3 (3 edges: 1?2?4 is longest)

Recursive Insight: Height of tree = 1 + max(height of left subtree, height of right subtree). Ye beautiful recursion hai � base case mein None ki height 0 hai. Har node apne dono children ki height puchta hai, bada wala leta hai, aur 1 add karta hai.

Max Depth vs Min Depth

Max depth aur min depth dono height se related hain but thoda alag hain:

# Max Depth = Height of tree (same cheez)
def maxDepth(node):
 if node is None:
 return 0
 return 1 + max(maxDepth(node.left), maxDepth(node.right))

# Min Depth = Root se sabse chhoti path
def minDepth(node):
 if node is None:
 return 0
 if node.left is None:
 return 1 + minDepth(node.right)
 if node.right is None:
 return 1 + minDepth(node.left)
 return 1 + min(minDepth(node.left), minDepth(node.right))

# Example:
# 1
# / \
# 2 3
# /
# 4
# Max Depth = 3 (1?2?4)
# Min Depth = 2 (1?3)

Min Depth Difference: Min depth mein ek twist hai � agar ek side mein subtree nahi hai (None hai), toh hum uss side ki depth count nahi karte. Kyunki None ki depth 0 hoti hai, but actual path mein None ek valid endpoint nahi hai.

Diameter of Binary Tree

Diameter = tree ki sabse lambi path ka length. Ye path root se guzar sakta hai ya nahi bhi � kisi bhi do nodes ke beech ka longest path. Diameter edges count karta hai.

def diameter(node):
 if node is None:
 return 0, 0 # (diameter, height)
 
 left_d, left_h = diameter(node.left)
 right_d, right_h = diameter(node.right)
 
 # Current node se guzarne wali longest path
 current_d = left_h + right_h
 
 # Maximum of: left diameter, right diameter, current path
 max_d = max(left_d, right_d, current_d)
 height = 1 + max(left_h, right_h)
 
 return max_d, height

# Efficient O(n) solution � ek hi pass mein

Diameter Pattern: Har node pe socho � sabse lambi path ya toh left subtree mein hai, ya right mein, ya current node se guzar rahi hai (left height + right height). Ye 3 possibilities check karo aur maximum lo. Height ka return karna zaroori hai kyunki parent nodes ko chahiye.

Balanced Binary Tree Check

Tree balanced hai agar har node ke left aur right subtree ki height ka difference 1 se zyada na ho. Ye O(n�) naive approach se O(n) optimal tak ja sakte ho:

# Naive O(n�) approach
def isBalanced(node):
 if node is None:
 return True
 
 left_height = height(node.left)
 right_height = height(node.right)
 
 if abs(left_height - right_height) > 1:
 return False
 
 return isBalanced(node.left) and isBalanced(node.right)

# Optimal O(n) approach � bottom-up
def isBalancedOptimal(node):
 def check(node):
 if node is None:
 return 0
 left = check(node.left)
 if left == -1:
 return -1 # Not balanced
 right = check(node.right)
 if right == -1:
 return -1 # Not balanced
 if abs(left - right) > 1:
 return -1
 return 1 + max(left, right)
 
 return check(node) != -1

Optimized Approach: Naive approach mein har node ke liye height alag se calculate ho rahi hai � O(n�). Optimal approach mein hum height ke saath balanced check bhi kar lete hain � ek hi pass mein sab ho jaata hai. Agar koi subtree unbalanced hai toh -1 return kar do, ye signal hai ki tree balanced nahi hai.

Try it: code khud likho

Exercise

Question: Given tree [1, 2, 3, 4, 5] (root=1, left=2, right=3, left.left=4, left.right=5), tree ki height kya hogi✓ Sirf number daalo.

Question: Same tree [1, 2, 3, 4, 5] ka diameter kya hoga✓ Sirf number daalo (edges count).

Common mistakes

Height mein nodes count karna: Height edges count karta hai, nodes nahi. Single node tree ki height 0 hoti hai, 1 nahi (agar convention 0-based hai).
Min Depth mein None count karna: Min depth mein agar ek side None hai toh uss side ki depth count mat karo. None valid endpoint nahi hai.
Diameter sirf root se sochna: Diameter root se guzar zaroori nahi hai. Longest path kisi bhi do nodes ke beech ho sakti hai.
Balance check O(n�) karna: Har node ke liye alag se height mat nikalo. Bottom-up approach use karo jo O(n) mein sab kar deta hai.
Skewed tree ka height: Skewed tree (linked list jaisa) ki height n hoti hai (jahan n = nodes). Balanced tree ki height log(n) hoti hai.

Lesson complete?

Height, diameter, aur balanced tree samajh aa gaya✓ Ab LCA (Lowest Common Ancestor) aur path problems seekhte hain � ye interview favourites hain.