Lowest Common Ancestor (BST)
Problem Statement
Given two nodes in a BST, find their Lowest Common Ancestor (LCA).
Example: Input: root=[6,2,8,0,4,7,9,null,null,3,5], p=2, q=8 → Output: 6
Approach: BST Property
Explanation: If both nodes are less than root, go left. If both greater, go right. Otherwise, root is LCA.
Time Complexity: O(h)
Space Complexity: O(h) recursion stack
function LCA(node, p, q):
if node == NULL: return NULL
if p.val < node.val and q.val < node.val:
return LCA(node.left, p, q)
if p.val > node.val and q.val > node.val:
return LCA(node.right, p, q)
return node
💡 Think: If both < root go left; if both > root go right; else current root is the LCA.