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ái1 < 5và con phải6 > 5(thỏa mãn cục bộ). - Tại nút
6: con trái3 < 6và con phải7 > 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ả:
- 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.valvà mọi nút bên phải lớn hơnu.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. - Phạm vi giá trị của
u.vallà bao nhiêu? Đề bài rất hay gài test có nút mang giá trị đúng bằngINT_MIN(-2147483648) hoặcINT_MAX(2147483647). Nếu bạn khởi tạolo = INT_MIN,hi = INT_MAXrồi báo sai khiv <= lohoặcv >= 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). - 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).
Để 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.
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 <= lohoặcu.val >= hi, nútuđã vi phạm ràng buộc của một tổ tiên nào đó phía trên → trả vềfalsengay 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.leftphải nằm trong khoảng(lo, u.val). - Nhánh phải
u.rightphải nằm trong khoảng(u.val, hi).
- Nhánh trái
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;
}
import math
import sys
def is_valid_bst(vals: list[str], u: int = 0, lo: float = -math.inf, hi: float = math.inf) -> bool:
if u >= len(vals) or vals[u] == "null":
return True
v = int(vals[u])
if not (lo < v < hi):
return False
return is_valid_bst(vals, 2 * u + 1, lo, v) and is_valid_bst(vals, 2 * u + 2, v, hi)
def main() -> None:
tokens = sys.stdin.read().split()
if not tokens or int(tokens[0]) == 0:
print("YES")
return
n = int(tokens[0])
vals = tokens[1 : 1 + n]
print("YES" if is_valid_bst(vals) else "NO")
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
static boolean isValidBst(String[] vals, int u, long lo, long hi) {
if (u >= vals.length || vals[u].equals("null")) return true;
long v = Long.parseLong(vals[u]);
if (v <= lo || v >= hi) return false;
return isValidBst(vals, 2 * u + 1, lo, v) &&
isValidBst(vals, 2 * u + 2, v, hi);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) {
System.out.println("YES");
return;
}
int n = sc.nextInt();
if (n == 0) {
System.out.println("YES");
return;
}
String[] vals = new String[n];
for (int i = 0; i < n; i++) vals[i] = sc.next();
boolean ok = isValidBst(vals, 0, Long.MIN_VALUE, Long.MAX_VALUE);
System.out.println(ok ? "YES" : "NO");
}
}
Độ 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ánhO(1). - Bộ nhớ phụ:
O(H)vớiHlà 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
- Dùng
INT_MINvàINT_MAXlàm giá trị khởi tạo cholovà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ệnv >= hisẽ trả vềfalsesai. Hãy luôn nâng kiểu biên lênlong long(LLONG_MIN,LLONG_MAX), dùng-math.inf / math.inftrong Python, hoặc truyền con trỏ nútTreeNode* lo_node, TreeNode* hi_node. - 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ốc2và con trái2, biểu thứcv < lo || v > hisẽ bỏ lọt vì2không lớn hơnhi = 2. Điều kiện bắt lỗi đúng phải làif (v <= lo || v >= hi) return false;. - Dùng biến toàn cục
prevtrong 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ĩnhprevgiữ 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ềnprevqua 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
2147483647hoặ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.
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.

