Lesson 4 � Intermediate

Lowest Common Ancestor & Path Problems

Trees mein path-based problems bahut aati hain � do nodes ka common ancestor kya hai, root se kisi node tak ka path kya hai, path ka sum kya hai. Ye sab recursion se solve hote hain aur interview mein 100% aate hain.

? 25 min✓ Intermediate✓ Binary Tree basics, Recursion

Lowest Common Ancestor (LCA)

WHAT

LCA = do nodes ka sabse neeche (deepest) common ancestor. MATLAB wo node jo dono nodes ka ancestor hai aur dono ke beech mein sabse neeche hai. Agar ek node doosre ka ancestor hai, toh wohi LCA hai.

WHEN

Relationship finding mein � family tree mein do logon ka common ancestor, network routing mein common path, ya kisi bhi problem mein jab do nodes ke beech ka path dhundhna ho.

WHERE

LeetCode pe 15+ LCA variations hain. Ye problem tree recursion ka perfect example hai � samjho toh bahut si problems easy ho jayengi.

# 1
# / \
# 2 3
# / \
# 4 5

# LCA(4, 5) = 2 (2 dono ka ancestor hai)
# LCA(4, 3) = 1 (1 dono ka ancestor hai)
# LCA(2, 3) = 1 (1 dono ka ancestor hai)
# LCA(4, 2) = 2 (2, 4 ka ancestor hai)

def lca(root, p, q):
 if root is None or root == p or root == q:
 return root
 
 left = lca(root.left, p, q)
 right = lca(root.right, p, q)
 
 if left and right:
 return root # Dono sides mein mila � ye hai LCA
 
 return left if left else right

# Time: O(n) � ek baar tree traverse karte hain
# Space: O(h) � recursion stack

LCA Magic: Har node pe socho � kya left subtree mein p ya q mila✓ Kya right subtree mein mila✓ Agar dono sides mein mila toh current node LCA hai. Agar sirf ek side mein mila toh wo side se answer aayega. Agar kisi mein nahi mila toh None return hoga.

Root to Node Path

Root se kisi specific node tak ka path dhundhna � ye recursion ka classic pattern hai. Path mein nodes ki list chahiye:

def root_to_node_path(root, target):
 if root is None:
 return []
 
 if root == target:
 return [root.val]
 
 left_path = root_to_node_path(root.left, target)
 if left_path:
 return [root.val] + left_path
 
 right_path = root_to_node_path(root.right, target)
 if right_path:
 return [root.val] + right_path
 
 return [] # Target is subtree mein nahi hai

# Example: root_to_node_path(root, node_5)
# Output: [1, 2, 5]

Pattern: Root se neeche jaate jaao. Agar target mil jaye toh uss node ki value list mein daalo aur return karo. Agar left se path mila toh current node ko path ke beginning mein add karo. Agar kisi se nahi mila toh empty list return karo.

Path Sum Problems

Ye problems check karti hain ki kya root se kisi leaf tak aisa path hai jiska sum target ke barabar ho. Ya kisi bhi node se kisi bhi node tak ka path sum target ke barabar ho:

# Path Sum I: Root se leaf tak target sum hai?
def hasPathSum(root, target):
 if root is None:
 return False
 
 if root.left is None and root.right is None:
 return root.val == target
 
 remaining = target - root.val
 return hasPathSum(root.left, remaining) or hasPathSum(root.right, remaining)

# Path Sum II: Root se leaf tak saare paths jo target sum de
def pathSum(root, target):
 result = []
 
 def dfs(node, remaining, path):
 if node is None:
 return
 path.append(node.val)
 if node.left is None and node.right is None:
 if remaining == node.val:
 result.append(path[:])
 dfs(node.left, remaining - node.val, path)
 dfs(node.right, remaining - node.val, path)
 path.pop() # Backtrack
 
 dfs(root, target, [])
 return result

Backtracking Pattern: Path problems mein recursion ke saath backtracking hoti hai. Node add karo, neeche jaao, aur wapas aake node hata do (pop). Isse har possible path explore hota hai without extra space.

Maximum Path Sum

Ye problem thodi tricky hai � kisi bhi node se kisi bhi node tak ka maximum sum path dhundho. Path root se guzar zaroori nahi hai:

def maxPathSum(root):
 max_sum = float('-inf')
 
 def gain(node):
 nonlocal max_sum
 if node is None:
 return 0
 
 left_gain = max(gain(node.left), 0) # Negative hai toh 0 lo
 right_gain = max(gain(node.right), 0)
 
 # Current node se guzarne wala maximum path
 price = node.val + left_gain + right_gain
 max_sum = max(max_sum, price)
 
 # Parent ko ek side ka path do
 return node.val + max(left_gain, right_gain)
 
 gain(root)
 return max_sum

# Key: Negative gains ko 0 se replace karo
# Kyunki path mein negative nodes include karna
# beneficial nahi hai

Max Path Sum Insight: Har node pe 2 decisions hain � (1) Current node se guzarne wala maximum path = left_gain + right_gain + node.val, (2) Parent ko return karo = node.val + max(left, right). Max path sum ke liye option 1 se global max update karo, parent ke liye option 2 return karo.

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), LCA of nodes 4 aur 3 ka value kya hoga✓ Sirf number daalo.

Question: Same tree mein root se leaf tak ka path 1?2?5 ka sum kya hoga✓ Sirf number daalo.

Common mistakes

LCA mein dono nodes ek subtree mein hain: Agar p aur q dono left subtree mein hain toh LCA bhi left subtree mein hoga. Root return mat karo � left se answer aayega.
Path sum mein leaf check bhoolna: Path sum tabhi valid hai jab path leaf node pe end ho. Sirf node milne se kaam nahi chalega.
Max path sum mein negative gains: Agar left ya right subtree ka gain negative hai toh usse include mat karo � 0 use karo. Negative path sum ko kharab karta hai.
Backtrack karna bhoolna: Path problems mein recursion se wapas aate waqt node hatao (pop). Nahi toh galat paths banenge.
LCA for BST vs Binary Tree: BST mein LCA property use karke O(h) mein solve kar sakte ho � agar p aur q dono root se chhote hain toh left jao, dono bade hain toh right jao. Binary Tree mein ye shortcut nahi hai.

Lesson complete?

LCA aur path problems samajh aa gayi✓ Ab tree construction seekhte hain � traversal arrays se tree kaise banate hain.