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