Phỏng vấn

Kiểm tra cây tìm kiếm nhị phân hợp lệ (Validate BST)

Sai lầm phổ biến nhất khi kiểm tra cây tìm kiếm nhị phân (Validate Binary Search Tree) là chỉ kiểm tra con trái nhỏ hơn cha và con phải lớn hơn cha tại từng nút cục bộ. Để đảm bảo tính chất BST trên toàn bộ cây con, bạn cần truyền khoảng giá trị cho phép (lo, hi) từ trên xuống hoặc kiểm tra dãy duyệt trung thứ tự (In-order) tăng ngặt.

Cái bẫy "chỉ so sánh với nút cha" và hợp đồng định nghĩa BST

Trong các buổi phỏng vấn thuật toán, bài toán Validate Binary Search Tree (kiểm tra một cây nhị phân có phải là cây tìm kiếm nhị phân hợp lệ hay không) được ưa chuộng không phải vì code dài, mà vì nó phát hiện ngay ứng viên có phân biệt được điều kiện cục bộ và bất biến toàn cục trên cây hay không.

Rất nhiều ứng viên vội vàng viết câu lệnh kiểm tra tại nút u: "Nếu u.left.val < u.val và u.right.val > u.val thì đệ quy xuống hai con." Cách viết này sai hoàn toàn trên những cây có độ sâu từ 2 trở lên! Hãy nhìn cây phản ví dụ trong Hình 1: gốc là 5, con trái của 5 là 1, con phải của 5 là 6; bên dưới nút 6 có con trái là 3 và con phải là 7. Nếu chỉ nhìn từng cặp cha - con trực tiếp:

  • Tại nút 5: con trái 1 < 5 và con phải 6 > 5 (thỏa mãn cục bộ).
  • Tại nút 6: con trái 3 < 6 và con phải 7 > 6 (cũng thỏa mãn cục bộ!).

Thế nhưng nút 3 lại nằm trong cây con bên phải của nút gốc 5, trong khi 3 nhỏ hơn 5! Theo định nghĩa chuẩn của Cây tìm kiếm nhị phân (BST), mọi nút trong cây con bên phải của 5 đều phải lớn hơn 5 một cách nghiêm ngặt.

Trước khi viết code, bạn hãy hỏi người phỏng vấn 3 câu hỏi để chốt đặc tả:

  1. BST có cho phép các nút mang giá trị trùng nhau không? Trong hầu hết các bài phỏng vấn (như LeetCode 98), BST yêu cầu bất đẳng thức nghiêm ngặt: mọi nút bên trái nhỏ hơn u.val và mọi nút bên phải lớn hơn u.val (nếu có hai nút bằng nhau như [2, 2, 2] thì trả về false). Nếu đề bài cho phép trùng ở một bên (ví dụ bên trái không vượt quá u.val), bạn chỉ cần đổi phép so sánh tương ứng.
  2. Phạm vi giá trị của u.val là bao nhiêu? Đề bài rất hay gài test có nút mang giá trị đúng bằng INT_MIN (-2147483648) hoặc INT_MAX (2147483647). Nếu bạn khởi tạo lo = INT_MIN, hi = INT_MAX rồi báo sai khi v <= lo hoặc v >= hi, chương trình sẽ báo sai oan cho cây chỉ có đúng 1 nút [2147483647] (vì v >= hi) hoặc [-2147483648] (vì v <= lo).
  3. Cây rỗng (root == null) có được coi là BST hợp lệ không? Theo quy ước toán học, cây rỗng luôn là một BST hợp lệ (true).
Ý chính

Để một cây nhị phân là BST hợp lệ, mỗi nút u không chỉ bị chặn bởi cha trực tiếp mà bị chặn bởi một khoảng mở (lo, hi) thu hẹp dần từ mọi tổ tiên trên đường đi từ gốc xuống: khi rẽ sang con trái của u, cận trên cập nhật thành hi = u.val; khi rẽ sang con phải của u, cận dưới cập nhật thành lo = u.val.

Bẫy kiểm tra BST cục bộ vs Truyền khoảng hợp lệ (lo, hi) 5 (-∞, +∞) 1 (-∞, 5) ✓ 6 (5, +∞) ✓ 3 Cần thuộc khoảng (5, 6)! 3 < 6 nhưng 3 <= gốc 5 → SAI 7 (6, +∞) ✓ Mọi nút ở cây con phải của 5 đều phải > 5 · Dùng kiểu 64-bit cho (lo, hi)
Validate BST: [5, 1, 6, null, null, 3, 7] Truyền khoảng hợp lệ (lo, hi) xuống từng nút Gốc 5 ∈ (-∞, +∞) → Hợp lệ Trái nhận (-∞, 5) · Phải nhận (5, +∞) Trái: 1 ∈ (-∞, 5) Hợp lệ ✓ Phải: 6 ∈ (5, +∞) Hợp lệ ✓ Con trái của 6 là 3: cần ∈ (5, 6) 3 <= 5 (vi phạm cận dưới 5) → SAI! Kết luận: Không phải BST (NO)
Hình 1. Quá trình truyền khoảng mở (lo, hi) trên cây [5, 1, 6, null, null, 3, 7]: khi từ gốc 5 rẽ phải sang 6 rồi rẽ trái sang 3, khoảng hợp lệ bị kẹp thành (5, 6), phát hiện ngay nút 3 vi phạm vì 3 không lớn hơn 5.

Hai phương pháp chuẩn xác: Truyền khoảng (lo, hi) từ trên xuống và Duyệt trung thứ tự (In-order)

Có hai cách tiếp cận đều đạt độ phức tạp tối ưu O(n) và bổ trợ trực tiếp cho các câu hỏi mở rộng tiếp theo trong buổi phỏng vấn:

Cách 1: Đệ quy truyền khoảng hợp lệ (lo, hi) (Top-Down Range DFS)

Ta bắt đầu tại gốc root với khoảng mở không giới hạn (-∞, +∞). Trong C++17 và Java 21, khi giá trị nút nằm trong kiểu int 32-bit, cách đơn giản và sạch nhất để biểu diễn (-∞, +∞) là dùng kiểu 64-bit long long (LLONG_MIN, LLONG_MAX trong C++; Long.MIN_VALUE, Long.MAX_VALUE trong Java), hoặc truyền con trỏ TreeNode* min_node, TreeNode* max_node (ban đầu bằng nullptr).

Tại mỗi nút u:

  • Nếu u == null, trả về true.
  • Nếu u.val <= lo hoặc u.val >= hi, nút u đã vi phạm ràng buộc của một tổ tiên nào đó phía trên → trả về false ngay lập tức.
  • Ngược lại, gọi đệ quy kiểm tra đồng thời hai nhánh:
    • Nhánh trái u.left phải nằm trong khoảng (lo, u.val).
    • Nhánh phải u.right phải nằm trong khoảng (u.val, hi).

Cách 2: Duyệt trung thứ tự (In-order Traversal) tăng ngặt

Một định lý nền tảng của cấu trúc dữ liệu cây phát biểu rằng: Phép duyệt trung thứ tự (Trái → Gốc → Phải) trên một cây nhị phân sinh ra một dãy số tăng ngặt khi và chỉ khi cây đó là một BST hợp lệ.

Nhờ tính chất này, thay vì lưu toàn bộ dãy In-order vào mảng rồi kiểm tra a[i] < a[i + 1], bạn chỉ cần giữ đúng một biến prev lưu giá trị của nút vừa thăm ngay trước đó trong thứ tự In-order: mỗi khi thăm tới nút hiện tại u, ta kiểm tra u.val > prev rồi cập nhật prev = u.val. Cách tư duy In-order này còn giúp giải quyết luôn bài toán Tìm phần tử nhỏ thứ k trong BST (Kth Smallest Element in a BST) và Khôi phục BST bị tráo đổi 2 nút (Recover BST).

Chạy tay từng bước trên hai cây mẫu

Hãy chạy tay phương pháp truyền khoảng (lo, hi) trên cây sai [5, 1, 6, null, null, 3, 7] (biểu diễn mảng theo mức từ chỉ số 0 đến 6):

Lượt gọi DFS Chỉ số u và giá trị val Khoảng cho phép (lo, hi) nhận từ cha Kiểm tra thuộc khoảng (lo, hi) Khoảng truyền xuống con trái và con phải
1 u = 0, val = 5 (Gốc) (-∞, +∞) 5 thuộc (-∞, +∞) (Đúng) Trái u = 1: (-∞, 5) · Phải u = 2: (5, +∞)
2 u = 1, val = 1 (-∞, 5) 1 thuộc (-∞, 5) (Đúng) Hai con của nút 1 đều là null → trả về true
3 u = 2, val = 6 (5, +∞) 6 thuộc (5, +∞) (Đúng) Trái u = 5: (5, 6) · Phải u = 6: (6, +∞)
4 u = 5, val = 3 (Con trái của 6) (5, 6) 3 không thuộc (5, 6) → SAI! Dừng ngay lập tức và trả về false (NO)

Nếu kiểm tra cùng cây [5, 1, 6, null, null, 3, 7] bằng phép duyệt In-order (Trái → Gốc → Phải), thứ tự các nút được thăm sẽ là: 1 -> 5 -> 3 -> 6 -> 7. Ngay khi đi từ 5 sang 3, ta phát hiện 3 nhỏ hơn 5 (dãy bị giảm xuống thay vì tăng ngặt), nên cũng kết luận cây không phải là BST.

Code mẫu C++17, Python và Java 21

Chương trình dưới đây đọc cây nhị phân dạng mảng đánh chỉ số kiểu heap (con của nút u ở 2u + 1 và 2u + 2, "null" là nút khuyết; khác chuỗi của LeetCode, vốn bỏ qua con của nút null) và kiểm tra tính hợp lệ của BST bằng phương pháp truyền khoảng (lo, hi) 64-bit, in ra "YES" nếu hợp lệ và "NO" nếu vi phạm.

#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool dfs_valid(const vector<string>& vals, int u, long long lo, long long hi) {
    if (u >= (int)vals.size() || vals[u] == "null") return true;
    long long v = stoll(vals[u]);
    if (v <= lo || v >= hi) return false;
    return dfs_valid(vals, 2 * u + 1, lo, v) &&
           dfs_valid(vals, 2 * u + 2, v, hi);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n) || n == 0) {
        cout << "YES\n";
        return 0;
    }
    vector<string> vals(n);
    for (int i = 0; i < n; i++) cin >> vals[i];
    bool ok = dfs_valid(vals, 0, LLONG_MIN, LLONG_MAX);
    cout << (ok ? "YES\n" : "NO\n");
    return 0;
}

Độ phức tạp thời gian và bộ nhớ

  • Thời gian: O(n) trong trường hợp xấu nhất (khi cây là BST hợp lệ hoặc nút vi phạm nằm ở nhánh cuối cùng), vì mỗi nút trên cây được thăm tối đa 1 lần với phép so sánh O(1).
  • Bộ nhớ phụ: O(H) với H là chiều cao của cây để lưu ngăn xếp lời gọi đệ quy (O(log n) nếu cây cân bằng, và O(n) trong trường hợp xấu nhất khi cây suy biến thành chuỗi thẳng).

Hệ thống hóa các bài toán phỏng vấn họ BST dùng chung tư duy

Một khi đã nắm vững hai vũ khí của BST là thu hẹp khoảng (lo, hi) và duyệt In-order tạo dãy tăng dần, bạn có thể giải quyết trọn vẹn cả cụm bài BST trong lộ trình Interview-150:

Bài toán phỏng vấn Vũ khí chủ lực Cách thực hiện trong O(n) hoặc O(H)
Validate Binary Search Tree Khoảng (lo, hi) hoặc In-order Kiểm tra lo < u.val < hi ở mọi nút, hoặc kiểm tra u.val > prev khi duyệt trung thứ tự
Kth Smallest Element in a BST Duyệt In-order đếm bước Duyệt Trái → Gốc → Phải bằng đệ quy hoặc ngăn xếp tường minh; mỗi lần thăm gốc thì giảm k, khi k == 0 trả về ngay u.val trong O(H + k)
Minimum Absolute Difference in BST Duyệt In-order giữ prev Trên dãy tăng dần, hiệu nhỏ nhất chắc chắn nằm giữa 2 phần tử kề nhau; cập nhật ans = min(ans, u.val - prev)
Lowest Common Ancestor (LCA) of a BST Tính chất phân nhánh của BST Từ gốc, nếu cả p, q < u.val thì rẽ trái; nếu cả p, q > u.val thì rẽ phải; nút đầu tiên nằm giữa p và q chính là LCA trong O(H) và O(1) bộ nhớ
Convert Sorted Array to BST Chia để trị ngược với In-order Chọn phần tử chính giữa mid của đoạn [l..r] làm gốc để đảm bảo cây cân bằng chiều cao O(log n)

Những lỗi sai dễ mất điểm và cách tự kiểm tra code

  1. Dùng INT_MIN và INT_MAX làm giá trị khởi tạo cho lo và hi: Như đã phân tích ở đầu bài, nếu đề bài có test cây 1 nút [2147483647] (INT_MAX), điều kiện v >= hi sẽ trả về false sai. Hãy luôn nâng kiểu biên lên long long (LLONG_MIN, LLONG_MAX), dùng -math.inf / math.inf trong Python, hoặc truyền con trỏ nút TreeNode* lo_node, TreeNode* hi_node.
  2. Dùng dấu < thay vì <= khi bắt lỗi vi phạm (if (v < lo || v > hi)): Nếu cây có hai nút bằng nhau như gốc 2 và con trái 2, biểu thức v < lo || v > hi sẽ bỏ lọt vì 2 không lớn hơn hi = 2. Điều kiện bắt lỗi đúng phải là if (v <= lo || v >= hi) return false;.
  3. Dùng biến toàn cục prev trong cách duyệt In-order mà quên khởi tạo lại giữa các test: Nếu làm trên nền tảng chấm nhiều test trong cùng một tiến trình, biến toàn cục/tĩnh prev giữ lại giá trị lớn từ test trước sẽ làm toàn bộ các test sau trả về false. Hãy truyền prev qua tham chiếu hoặc đặt làm thuộc tính khởi tạo mới trong mỗi lần gọi hàm.

Để tự kiểm tra code của mình, bạn có thể viết thêm hàm duyệt trung thứ tự thu toàn bộ giá trị vào mảng inorder rồi kiểm tra phần tử đứng sau lớn hơn phần tử đứng trước (inorder[i + 1] > inorder[i]) với mọi i, sau đó đối chiếu với hàm đệ quy khoảng (lo, hi) trên 4 bộ test biên:

  • Cây hợp lệ chuẩn: [2, 1, 3] → YES.
  • Cây bẫy vi phạm ở tầng cháu: [5, 1, 6, null, null, 3, 7] → NO.
  • Cây có giá trị trùng nhau: [2, 2, 2] → NO.
  • Cây có nút mang giá trị biên 32-bit 2147483647 hoặc -2147483648 đứng một mình → YES.

Luyện ngay trên Big-O Coding

Bạn hãy thực hành ngay 3 bài toán kiểm tra tính chất BST, tìm phần tử nhỏ thứ K và tìm tổ tiên chung gần nhất trên BST trong lộ trình Coding Interview 150 dưới đây.

Câu hỏi thường gặp

Nếu giá trị nút trong cây cũng là kiểu 64-bit (long long) và có thể đạt tới LLONG_MIN hoặc LLONG_MAX thì làm sao truyền khoảng (lo, hi)?

Khi bản thân dữ liệu đã dùng hết phạm vi 64-bit, bạn không cần tìm một số nhỏ hơn LLONG_MIN nữa mà chỉ cần truyền con trỏ tới nút biên (const TreeNode* lo_node, const TreeNode* hi_node, hoặc Integer / Long có thể nhận giá trị null trong Java, Optional trong C++17). Nếu lo_node != nullptr && u->val <= lo_node->val thì báo sai; lúc đầu gọi từ gốc thì truyền hai con trỏ nullptr. Cách này hoàn toàn độc lập với kiểu số của nút.

Giữa cách truyền khoảng (lo, hi) và cách duyệt In-order, người phỏng vấn thích cách nào hơn?

Cả hai cách đều được đánh giá tối đa nếu bạn cài đặt sạch sẽ. Cách truyền khoảng (lo, hi) thường ngắn hơn vài dòng và dừng sớm ngay khi phát hiện một nhánh phía trên vi phạm mà không cần đi xuống đáy nhánh trái trước như In-order. Tuy nhiên, bạn nên chủ động nhắc thêm một câu về tính chất dãy In-order tăng ngặt, vì câu hỏi phụ tiếp theo của người phỏng vấn rất hay chuyển sang bài Kth Smallest Element in a BST.

Có cách nào kiểm tra BST với bộ nhớ phụ O(1) mà không dùng ngăn xếp đệ quy O(H) không?

Có, đó là thuật toán duyệt cây Morris (Morris In-order Traversal). Kỹ thuật này tận dụng con trỏ right đang rỗng của nút tiền nhiệm trung thứ tự (in-order predecessor) để nối tạm thời quay về nút hiện tại, giúp đi xuống rồi quay lên mà không cần ngăn xếp. Lưu ý rằng nếu dùng Morris Traversal để kiểm tra BST, bạn không được return false thoát sớm khi chưa tháo hết các liên kết tạm đã nối, nhằm giữ nguyên cấu trúc cây ban đầu.

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483