Cấu trúc BST nói cho bạn biết ancestor nằm ở đâu trước khi bạn tìm

Bài toán cho bạn một BST và hai node p, q đều tồn tại trong đó. Tìm lowest common ancestor — node sâu nhất có cả hai làm descendant, với quy ước rằng một node có thể là descendant của chính nó.

Định nghĩa LCA giống nhau với mọi binary tree, nhưng cấu trúc BST thay đổi hoàn toàn cách bạn tìm nó. Với binary tree thông thường, bạn không còn lựa chọn nào khác ngoài việc tìm kiếm cả hai subtree. Với BST, invariant sắp xếp — mọi node ở subtree trái đều nhỏ hơn, mọi node ở subtree phải đều lớn hơn — cho phép bạn điều hướng thay vì tìm kiếm.

BST dùng trong cả hai ví dụ. Với p=2, q=8: tại node 6, một target nằm trái và một nằm phải — tìm thấy điểm phân kỳ ngay lập tức. Với p=2, q=4: cả hai đều trái của 6, đi trái; tại node 2, chính p là root — node 2 là LCA.

Đề bài

Cho một binary search tree (BST) và hai node p, q trong cây, tìm lowest common ancestor (LCA) của chúng. LCA được định nghĩa là node sâu nhất có cả p lẫn q là descendant, trong đó một node được tính là descendant của chính nó. Đề gốc: LeetCode 235.

Ràng buộc:
- Số node trong cây nằm trong khoảng [2, 10^5].
- -10^9 <= Node.val <= 10^9
- Tất cả Node.val đều unique.
- p != q
- p và q đều tồn tại trong BST.

Constraints buộc bạn làm gì

Số node: [2, 10^5]. Giá trị: [-10^9, 10^9], tất cả unique. Cả p và q đều được đảm bảo tồn tại.

Số node cho phép giải pháp O(N) — 10^5 node với traversal đơn giản là ổn về thời gian. Nhưng từ "unique" mới là thứ mở khóa cách tiếp cận BST: vì không có hai node nào cùng giá trị, phép so sánh là rõ ràng và không mơ hồ.

Đảm bảo rằng p và q đều tồn tại nghĩa là bạn không bao giờ cần xử lý trường hợp "không tìm thấy target". Vòng lặp iterative có thể trả về None trên giấy, nhưng thực tế constraints nói rằng dòng đó không bao giờ được thực thi.

p != q loại bỏ trường hợp suy biến khi cả hai target là cùng một node. Dải giá trị [-10^9, 10^9] có nghĩa là giá trị có thể âm — các toán tử so sánh < và > vẫn hoạt động đúng, không cần xử lý đặc biệt.

Approach 1: brute-force DFS trên binary tree

Trước khi dùng BST property, nên hiểu giải pháp binary tree tổng quát làm gì. Cách này chạy trên bất kỳ binary tree nào, không chỉ BST.

Logic: với mỗi node, kiểm tra xem p và q có ở các subtree khác nhau không (điều này làm node hiện tại là LCA) hay ở cùng một subtree (recurse về phía đó). Base case xử lý việc tìm thấy p hoặc q trực tiếp — khi gặp một trong hai target, trả nó lên; nếu cả hai subtree đều trả về kết quả non-null, node hiện tại là điểm phân kỳ.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
 
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
 
        if left and right:
            return root
 
        return left if left else right

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
 
        TreeNode left = LowestCommonAncestor(root.left, p, q);
        TreeNode right = LowestCommonAncestor(root.right, p, q);
 
        if (left != null && right != null) {
            return root;
        }
 
        return left != null ? left : right;
    }
}

Base case root == p || root == q xử lý tình huống một trong các target là ancestor của cái kia. Khi tìm thấy p, ta trả nó về mà không cần tìm tiếp. Nếu q nằm trong subtree của p, phía phải của recursion sẽ không tìm thấy gì và trả về null — left nhận p và right nhận null, ta trả về p. LCA là chính xác.

Trace tay: p=2, q=8 trên BST ví dụ

lowestCommonAncestor(root=6, p=2, q=8)
  root != p, root != q, recurse cả hai phía

  lowestCommonAncestor(root=2, p=2, q=8)
    root == p -> return node(2)   [kết quả trái]

  lowestCommonAncestor(root=8, p=2, q=8)
    root == q -> return node(8)   [kết quả phải]

  left=node(2), right=node(8), cả hai non-null -> return root=node(6)

Đáp án: 6  (đúng)

Thuật toán thăm root 6, rồi cả hai subtree. Tìm thấy cả hai target ở các subtree khác nhau, nên 6 là LCA. Thăm 3 trong 9 node trong trường hợp này, nhưng worst case phải thăm tất cả N node.

Complexity của brute-force

Time: O(N). Worst case — cây lệch, hoặc cả hai target sâu trong cùng một subtree — bạn thăm mọi node trước khi tìm được câu trả lời.

Space: O(H) cho call stack. H là chiều cao cây: O(log N) với cây cân bằng, O(N) với cây lệch hoàn toàn.

Đây là cách đúng. Nhưng với BST, nó lãng phí vì bỏ qua hoàn toàn cấu trúc.

Approach 2: dùng BST property để điều hướng trực tiếp

BST invariant nói với bạn chính xác mỗi giá trị nằm ở đâu tương đối với bất kỳ node nào. Nếu cả p.val và q.val đều nhỏ hơn current.val, cả hai node nằm trong subtree trái — đi trái. Nếu cả hai lớn hơn, đi phải. Ngay khi chúng ở hai phía khác nhau (hoặc một trong số chúng bằng node hiện tại), bạn đang ở LCA.

Không có tìm kiếm ở đây. Đây là điều hướng. Ordering invariant làm tất cả công việc.

Phiên bản iterative

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        p_val = p.val
        q_val = q.val
 
        current = root
 
        while current:
            current_val = current.val
 
            if p_val < current_val and q_val < current_val:
                current = current.left
            elif p_val > current_val and q_val > current_val:
                current = current.right
            else:
                return current
 
        return None  # không bao giờ đến đây theo constraints

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int pVal = p.val;
        int qVal = q.val;
 
        TreeNode current = root;
 
        while (current != null) {
            int currentVal = current.val;
 
            if (pVal < currentVal && qVal < currentVal) {
                current = current.left;
            }
            else if (pVal > currentVal && qVal > currentVal) {
                current = current.right;
            }
            else {
                return current;
            }
        }
 
        return null; // không bao giờ đến đây theo constraints
    }
}

Nhánh else bao phủ ba tình huống khác nhau, tất cả đều xác định đúng LCA:

• p.val < current.val và q.val > current.val (hoặc ngược lại): chúng ở hai phía đối diện
• p.val == current.val: p chính là node hiện tại, và vì cả p lẫn q đều thuộc subtree gốc ở p, p là LCA
• q.val == current.val: lý luận tương tự với q

Cả ba trường hợp gộp vào một nhánh vì toán học hoạt động đúng: nếu không phải "cả hai trái" cũng không phải "cả hai phải", bạn đang ở điểm phân kỳ.

Phiên bản recursive

Cùng logic viết dạng recursive — ngắn hơn, nhưng dùng O(H) stack space:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < root.val && q.val < root.val) {
            return LowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {
            return LowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

Phiên bản recursive dễ đọc hơn. Phiên bản iterative dùng O(1) space và tránh tăng stack cho cây sâu. Với n = 10^5 và BST lệch hoàn toàn, đó là 100.000 stack frame với cách recursive — đáng cân nhắc, dù giới hạn recursion của Python sẽ là vấn đề đầu tiên.

Trace tay: p=2, q=4 trên BST ví dụ

current = 6, p_val=2, q_val=4
  cả hai < 6 -> đi trái

current = 2, p_val=2, q_val=4
  p_val == current_val (2 == 2)
  -> không phải "cả hai trái" cũng không phải "cả hai phải" -> return node(2)

Đáp án: 2  (đúng, vì p=2 là ancestor của q=4)

Hai bước. Phiên bản brute-force cũng sẽ thăm node 4 (để xác nhận nó tồn tại trong subtree) trước khi trả về. Ở đây, ngay khi chạm vào p, logic so sánh kết thúc.

Complexity của BST approach

Time: O(H) trong đó H là chiều cao cây. Mỗi bước bạn di chuyển một level sâu hơn. Với BST cân bằng, H = O(log N). Với BST lệch hoàn toàn, H = O(N). Bài toán không đảm bảo cân bằng, nên nói O(H) và ghi chú hai trường hợp riêng.

Space: O(1) với phiên bản iterative — chỉ con trỏ current. O(H) với phiên bản recursive, do call stack.

Các edge case

Một target là ancestor của target kia (Ví dụ 2, p=2, q=4): vòng lặp iterative trả về ngay khi current.val bằng p_val hoặc q_val. Trong brute-force, trả về node tìm thấy ngay lập tức và để null từ phía kia kết hợp với nó là thứ xử lý trường hợp này. Cả hai cách đều đúng theo thiết kế.

Root là LCA (p=2, q=8 trong ví dụ): phép so sánh đầu tiên trong cách iterative nhấn nhánh else ngay tại root. Một phép so sánh, xong. Phiên bản brute-force recurse vào cả hai con, khám phá kết quả, rồi trả về trong quá trình unwind — thăm ít nhất ba node.

Cây chỉ có hai node ([2,1], p=2, q=1): root là 2, p là 2, q là 1. Trong cách iterative BST: p_val == current_val, nên không phải "cả hai trái" cũng không phải "cả hai phải", return root = node(2). Trong brute-force: root == p, return root ngay lập tức. Cả hai trả về 2. Đúng.

BST lệch sâu (chuỗi N node, p và q gần cuối): cả hai cách đều đi suốt chuỗi. Cách BST là O(N) ở đây. Brute-force cũng O(N) nhưng thăm nhiều node hơn vì phải xác nhận cả hai phía. Trong worst case lệch, BST iterative vẫn dùng O(1) space trong khi brute-force dùng O(N) stack space.

Giá trị âm: các toán tử < và > hoạt động đúng với số âm. BST có giá trị [-3, -5, -2] với root là -3, p=-5, q=-2 trả về -3 ngay bước đầu tiên (một bên trái, một bên phải). Không cần xử lý đặc biệt.

Bảng so sánh

H = O(log N) với cây cân bằng, O(N) với cây lệch.

Phiên bản nào tôi sẽ ship

Cách iterative BST. Lý luận đủ đơn giản để phát biểu trong một câu: cả hai target không thể ở cùng một subtree nếu giá trị node hiện tại nằm đúng giữa chúng hoặc bằng một trong hai. Câu đó chính là toàn bộ thuật toán. Code là bảy dòng Python, và mỗi dòng tương ứng trực tiếp với một nhánh của câu đó.

Tôi không ship phiên bản recursive BST trong production code cho hệ thống có thể gặp cây lệch theo bệnh lý. O(1) space của phiên bản iterative tốt hơn thực sự khi bạn không thể đảm bảo cân bằng. Trong coding interview, cả hai đều ổn — tôi sẽ đề cập sự khác biệt về space một cách rõ ràng.

Cách brute-force là câu trả lời cho một câu hỏi khác: "làm thế nào tìm LCA trong binary tree không có ordering invariant?" Đó là bài 236. Nên giữ nó trong đầu như một fallback — khi bài nói "binary tree" thay vì "BST", bạn không thể điều hướng; bạn phải tìm kiếm. Constraint "BST" mới là thứ làm cho điều hướng có thể ở đây.

Pattern cốt lõi: điều hướng vs. tìm kiếm trong cấu trúc có thứ tự

Bài LCA trong BST là một instance của pattern tổng quát: khi cấu trúc dữ liệu cung cấp đảm bảo sắp xếp, bạn có thể thay thế tìm kiếm (thăm cho đến khi tìm thấy) bằng điều hướng (suy luận về vị trí target phải nằm ở đâu và đi đến đó). Binary search trong array làm điều tương tự. BST search tự nó cũng vậy. Ở đây bạn đang điều hướng đến điểm phân kỳ thay vì đến một target duy nhất.

Nhận diện chính: LCA là node đầu tiên mà p và q không còn ở cùng một phía. Trong cây không có thứ tự, bạn không thể xác định "cùng phía" mà không thăm cả hai phía. Trong BST, bạn có thể. Đó là toàn bộ insight.

Vị trí trong series và bước tiếp theo

Trong series trees, bài này nằm sau Validate Binary Search Tree (98) và Kth Smallest Element in a BST (230). Hai bài đó đã thiết lập rằng BST invariant — subtree trái nhỏ hơn, subtree phải lớn hơn — là thứ bạn suy luận về, không chỉ là thứ làm cho search nhanh hơn. LCA 235 là ứng dụng: bạn dùng invariant để điều hướng thay vì tìm kiếm.

Lowest Common Ancestor of a Binary Tree (236) là companion tự nhiên. Cùng phát biểu bài toán với từ "BST" thay bằng "binary tree." Trick điều hướng biến mất hoàn toàn; bạn phải dùng brute-force DFS. So sánh giữa 235 và 236 là minh chứng rõ ràng nhất về thứ BST structure mang lại cho bạn.

Delete Node in a BST (450) áp dụng cùng pattern điều hướng. Bạn đi qua cây bằng BST comparison để tìm target, rồi tái cấu trúc subtree xung quanh nó. Phần đi-đến-target giống hệt những gì bạn làm ở đây.

Kth Smallest Element in a BST (230) cũng điều hướng bằng ordering nhưng dùng in-order traversal thay vì routing dựa trên so sánh. Sự tương phản thú vị: trong LCA bạn dùng < và > để route, trong Kth Smallest bạn dùng in-order count.

Insert into a BST (701) là ứng dụng đơn giản nhất: điều hướng đến vị trí null nơi node mới thuộc về, rồi chèn. Một BST comparison mỗi level, cùng O(H) time, và giúp xây dựng intuition về lý do pattern iterative là tự nhiên cho BST traversal.