Validate Binary Search Tree: tại sao chỉ kiểm tra node cha là sai

Định nghĩa của BST nghe có vẻ đơn giản: con trái nhỏ hơn cha, con phải lớn hơn cha. Viết một solution chỉ kiểm tra điều đó và bạn sẽ nhận Wrong Answer ngay từ ví dụ thứ hai. Định nghĩa là toàn cục, không phải cục bộ. Mọi node trong subtree trái phải nhỏ hơn tổ tiên phân tách chúng, dù tổ tiên đó ở bao nhiêu tầng phía trên. Sự khác biệt đó chính là lý do bài này đáng được nghiên cứu kỹ.

[5,1,4,null,null,3,6] vi phạm BST tại node 4 — nó nằm trong subtree phải của 5, nên phải lớn hơn 5. Nó không thỏa mãn. Một phép kiểm tra chỉ so sánh 4 > 1 (con trái của cha 4) sẽ pass sai. Giá trị của root truyền xuống thành lower bound cho mọi thứ ở phía phải của nó.

Ràng buộc ép buộc điều gì

n tối đa 10,000 không phải điểm áp lực. O(n) duyệt mỗi node một lần là target tự nhiên và đúng với cả hai approach. Ràng buộc thực sự quan trọng là range giá trị: -2^31 <= Node.val <= 2^31 - 1. Giá trị node trải rộng toàn bộ signed integer 32-bit, nghĩa là bạn không thể dùng int.MinValue và int.MaxValue làm bounds ban đầu trong C# — một node ở biên sẽ so sánh bằng với sentinel, không phải nhỏ hơn hay lớn hơn, và bạn sẽ trả về false sai cho cây hợp lệ chứa Integer.MIN_VALUE.

Trong Python điều này không gây vấn đề vì float('-inf') và float('inf') luôn nằm ngoài phạm vi integer. Trong C#, dùng long.MinValue và long.MaxValue làm bounds ban đầu. Signature hàm thay đổi thành Validate(TreeNode node, long minVal, long maxVal) — chi tiết này gây trúng nhiều người dưới áp lực phỏng vấn.

Ràng buộc khác: không có duplicate values được ngầm hiểu là vi phạm. Problem statement nói "strictly less than" và "strictly greater than", nên giá trị bằng nhau trong subtree trái hoặc phải đều fail. Điều kiện validation là node.val <= minVal || node.val >= maxVal, không phải < hay >.

Approach 1: Inorder traversal — khai thác tính chất dãy tăng dần

Một BST duyệt theo inorder (trái -> node -> phải) cho ra các giá trị theo thứ tự tăng dần nghiêm ngặt. Quan sát này cho phép bạn validate cây mà không cần theo dõi bounds: duyệt mỗi node theo inorder, kiểm tra mỗi giá trị phải lớn hơn giá trị trước.

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.prev = None
        return self._inorder(root)
 
    def _inorder(self, node: TreeNode) -> bool:
        if not node:
            return True
        if not self._inorder(node.left):
            return False
        if self.prev is not None and node.val <= self.prev:
            return False
        self.prev = node.val
        return self._inorder(node.right)

public class Solution {
    private long? prev = null;
 
    public bool IsValidBST(TreeNode root) {
        prev = null;
        return Inorder(root);
    }
 
    private bool Inorder(TreeNode node) {
        if (node == null) return true;
        if (!Inorder(node.left)) return false;
        if (prev.HasValue && node.val <= prev.Value) return false;
        prev = node.val;
        return Inorder(node.right);
    }
}

Phiên bản C# dùng long? cho prev — lý do tương tự. Giá trị node trải rộng phạm vi int, nên prev phải có thể giữ int.MinValue mà không bị nhầm lẫn.

Trace qua Ví dụ 2

Input: [5,1,4,null,null,3,6], tạo ra cây ở trên.

Gọi _inorder(5)
  -> gọi _inorder(1)
       -> gọi _inorder(null) [con trái của 1]: return True
       -> prev là None, set prev = 1
       -> gọi _inorder(null) [con phải của 1]: return True
     return True
  -> prev = 1, node.val = 5, 5 > 1 OK, set prev = 5
  -> gọi _inorder(4)
       -> gọi _inorder(3) [con trái của 4]
            -> gọi _inorder(null): return True
            -> prev = 5, node.val = 3, 3 <= 5 -> return False
         return False
     return False
  return False

Vi phạm xuất hiện tại node 3: inorder nói chúng ta nên thấy các giá trị lớn hơn 5 trong subtree phải của 5, nhưng 3 xuất hiện trước khi chúng ta rời subtree đó. Phép kiểm tra prev bắt được ngay lập tức.

Vấn đề với biến instance

Trạng thái prev sống trên instance (hoặc như closure variable trong Python). Hoạt động tốt cho một lần gọi isValidBST, nhưng nếu test framework — hoặc một variant của problem — gọi cùng một Solution object hai lần, prev mang theo từ lần gọi trước. Phiên bản C# explicitly reset prev = null trong IsValidBST vì lý do này. Trong Python, bạn có thể chuyển prev thành list cục bộ (prev = [None]) và mutate prev[0], tránh instance variable hoàn toàn và cho phép closure capture nó sạch hơn.

Đây không phải vấn đề về correctness trong thực tế trên LeetCode, nhưng là loại statefulness khiến approach này hơi dễ bị lỗi. Approach range validation tránh hoàn toàn điều đó.

Approach 2: Range validation — mang bounds theo trong recursion

Thay vì kiểm tra sau thực tế (dãy inorder), truyền interval hợp lệ xuống trước: mỗi node nhận lower bound và upper bound, và phải nằm nghiêm ngặt trong đó. Khi recurse trái, giá trị node hiện tại trở thành upper bound mới. Khi recurse phải, nó trở thành lower bound mới.

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def validate(node, min_val, max_val):
            if not node:
                return True
            if node.val <= min_val or node.val >= max_val:
                return False
            return (validate(node.left, min_val, node.val) and
                    validate(node.right, node.val, max_val))
 
        return validate(root, float('-inf'), float('inf'))

public class Solution {
    public bool IsValidBST(TreeNode root) {
        return Validate(root, long.MinValue, long.MaxValue);
    }
 
    private bool Validate(TreeNode node, long minVal, long maxVal) {
        if (node == null) return true;
        if (node.val <= minVal || node.val >= maxVal) return false;
        return Validate(node.left, minVal, node.val) &&
               Validate(node.right, node.val, maxVal);
    }
}

Không có instance state. Mỗi lần gọi recursion là self-contained. Bounds tích lũy khi bạn đi xuống: mỗi node thừa hưởng tất cả ràng buộc áp đặt bởi tổ tiên của nó, không chỉ cha trực tiếp.

Cách bounds lan truyền

Trace qua ví dụ fail, lần này với bounds:

• Root 5: bounds là (-∞, +∞). 5 nằm trong. Recurse trái với (-∞, 5), phải với (5, +∞).
• Node 1: bounds là (-∞, 5). 1 nằm trong.
• Node 4: bounds là (5, +∞). 4 <= 5 fail. Return false ngay lập tức.

Vi phạm được tìm thấy tại chính 4, không phải ở con của nó. Phép kiểm tra là node.val <= minVal, bắt được 4 <= 5. Không cần recurse thêm.

Short-circuit and trong cả Python và C# nghĩa là chúng ta không bao giờ visit node 3 hay 6 — một khi subtree trái của 4 không liên quan (chúng ta đã biết 4 fail), không cái nào được evaluate.

Tại sao đây là phiên bản tôi sẽ viết

Không có shared state. Hàm là pure: cùng input luôn cho cùng output, và không có dependency ngầm vào thứ tự gọi. Debug một hàm không có side effects dễ hơn nhiều so với debug một hàm phụ thuộc vào mutation của self.prev. Bounds cũng làm invariant hiển thị trực tiếp trong code: node.val <= minVal fail nghĩa là "node này phá vỡ contract được đặt bởi tổ tiên của nó." Điều đó phản ánh chính xác định nghĩa của bài toán.

Approach inorder yêu cầu bạn nội tâm hóa một tính chất (BST -> dãy inorder đã sort) và suy luận rằng vi phạm thứ tự sort chứng minh BST không hợp lệ. Suy luận đó đúng, nhưng là một mức độ gián tiếp mà approach range không cần.

Cả hai đều O(n) time và O(h) space. Complexity tiệm cận giống hệt nhau. Cho mọi thứ khác — clarity, statelessness, debuggability — range validation thắng. Đây là cái tôi ship.

Edge cases và code thực sự làm gì với chúng

Cây rỗng (root = null): cả hai approach return True ngay từ base case. Bài toán đảm bảo ít nhất một node, nhưng xử lý null vẫn là behavior đúng.

Node đơn (không có con): range validation kiểm tra giá trị với (-inf, +inf), luôn pass, sau đó recurse vào hai con null đều return true. Inorder traversal visit node đơn, prev là None nên không có so sánh nào xảy ra, và trả về true. Cả hai đúng.

Giá trị node tại INT_MIN hoặc INT_MAX: trong Python, không vấn đề — float('-inf') luôn nhỏ hơn bất kỳ integer nào, và float('inf') luôn lớn hơn. Trong C#, dùng long.MinValue và long.MaxValue có nghĩa là ngay cả node với val = Int32.MinValue vẫn thỏa node.val > long.MinValue mà không overflow. Nếu bạn dùng int.MinValue làm initial lower bound, thì root node với val = int.MinValue sẽ fail kiểm tra node.val <= minVal và return false cho cây một node hợp lệ. Đó là wrong answer cụ thể trên input hợp lệ.

Duplicate values (ví dụ cây mà con trái bằng cha): strict inequalities < minVal -> fail, > maxVal -> fail bắt được điều này. Node bằng giá trị tổ tiên vi phạm định nghĩa BST ("strictly less than", "strictly greater than"). Cả hai approach xử lý duplicate đúng: inorder check node.val <= self.prev reject bằng, range check node.val <= minVal reject bằng.

Skewed tree (chuỗi degenerate của 10,000 node): độ sâu recursion đạt O(n) = 10,000 frame. Giới hạn recursion mặc định của Python là 1,000. Trên LeetCode điều này thường được tăng lên, nhưng nếu bạn gặp RecursionError với approach inorder, bạn có thể tăng giới hạn bằng sys.setrecursionlimit(20000) hoặc viết lại theo kiểu iterative. Ràng buộc n <= 10^4 chính xác là nơi điều này trở thành mối quan tâm thực tế — không phải lý thuyết.

Bảng so sánh complexity

Cả hai visit mỗi node đúng một lần và thực hiện O(1) công việc mỗi node. Space là độ sâu call stack, là O(h). Trên balanced tree là O(log n); trên degenerate tree (input đã sort) là O(n). Không approach nào có complexity tiệm cận tốt hơn — sự khác biệt nằm ở chất lượng code, không phải hiệu năng.

Vị trí trong series

Đây là bài thứ sáu trong trees series, và là bài đầu tiên yêu cầu bạn validate một ràng buộc trên toàn bộ subtree thay vì một node đơn hay một đường đi. Invert Binary Tree (226), Maximum Depth of Binary Tree (104), và Same Tree (100) đều làm gì đó tại một node và kết hợp kết quả — nhưng không cái nào yêu cầu thông tin từ tổ tiên. Bài này thì có. Approach range validation giới thiệu pattern mang theo state tích lũy xuống dưới qua các lần gọi recursion, xuất hiện lại trong các bài liên quan đến path sums với targets và subtree queries với context bên ngoài.

Kth Smallest Element in a BST (230) dùng tính chất sorted inorder trực tiếp hơn: thay vì kiểm tra thứ tự, bạn dùng inorder traversal để tìm phần tử thứ k theo số lần visit. Cấu trúc traversal giống hệt Approach 1 ở đây; aggregation khác.

Lowest Common Ancestor of a BST (235) khai thác tính chất BST theo hướng khác — bạn dùng ordering để quyết định descend vào subtree nào, cắt bài toán xuống O(h) thay vì O(n). So sánh với LCA của binary tree tổng quát, nơi bạn không thể dùng ordering gì cả.

Insert into a BST (701) và Delete Node in a BST (450) hoàn thiện các thao tác BST cốt lõi. Khi bạn đã thoải mái với BST ordering invariant từ validation, insertion và deletion cảm thấy tự nhiên — cả hai đều là recursive descent dùng cùng bounds reasoning, chỉ thêm structural modification ở cuối.