Lowest Common Ancestor of a BST

Bài toán

Cho một cây tìm kiếm nhị phân (Binary Search Tree - BST) và hai node p, q. Tìm tổ tiên chung gần nhất (LCA - Lowest Common Ancestor) của chúng. Định nghĩa LCA: Node x là LCA của p và q nếu x là tổ tiên của cả hai (hoặc chính là một trong hai) và x nằm sâu nhất có thể.

Phân Tích & Tiếp Cận

Tính chất BST

• Mọi node bên trái < Root.
• Mọi node bên phải > Root.

Logic Tìm kiếm

Bắt đầu từ Root:

1. Nếu cả p và q đều lớn hơn Root -> LCA chắc chắn nằm bên nhánh Phải. (Move Right).
2. Nếu cả p và q đều nhỏ hơn Root -> LCA chắc chắn nằm bên nhánh Trái. (Move Left).
3. Nếu (p < Root < q) hoặc (q < Root < p) hoặc Root là p hoặc Root là q -> Thì Root chính là điểm phân tách (Split Point) đầu tiên. => Root chính là LCA.

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    let curr = root;

    while (curr) {
        if (p!.val > curr.val && q!.val > curr.val) {
            curr = curr.right;
        } else if (p!.val < curr.val && q!.val < curr.val) {
            curr = curr.left;
        } else {
            return curr; // Đây là điểm chia tách
        }
    }
    return null;
}

• Time Complexity: $O(h)$ - Hoặc $O(\log n)$ với cây cân bằng. Ta chỉ đi xuống 1 nhánh.
• Space Complexity: $O(1)$ - Dùng vòng lặp thay vì đệ quy.