Phần tử nhỏ thứ K trong BST: in-order traversal như một dòng dữ liệu đã sắp xếp

Một binary search tree đã mã hóa thứ tự sắp xếp bên trong cấu trúc của nó. Nghe có vẻ hiển nhiên nhưng đó chính là toàn bộ bài toán. Left subtree của bất kỳ node nào chỉ chứa các giá trị nhỏ hơn node đó; right subtree chỉ chứa các giá trị lớn hơn. Nếu bạn duyệt BST theo thứ tự left-root-right — tức là in-order traversal — các node xuất hiện theo thứ tự tăng dần. Mọi node, không có ngoại lệ, được đảm bảo bởi BST invariant. Tìm phần tử nhỏ thứ k khi đó chỉ là đếm trong lúc đi bộ qua cây và dừng khi đếm đến k.

Câu hỏi thực sự là bạn có tận dụng thứ tự sắp xếp đó hay bỏ qua nó.

Ràng buộc quyết định gì

1 <= k <= n <= 10^4 với 0 <= Node.val <= 10^4. Bảo đảm k hợp lệ (k <= n) có nghĩa là bạn không bao giờ phải xử lý "k vượt quá số node" — bài toán hứa rằng k luôn trỏ đến một node thực sự tồn tại. Giới hạn trên 10^4 node nghĩa là O(n log n) hoàn toàn chấp nhận được về mặt thời gian, nhưng O(n) đạt được mà không cần thêm bất kỳ cơ chế nào, vì vậy không có lý do gì để chấp nhận kém hơn.

Cây bên dưới là ví dụ 2: root = [5,3,6,2,4,null,null,1], k=3.

In-order visit theo thứ tự: 1, 2, 3, 4, 5, 6. Node thứ ba được visit là 3. Kết quả: 3.

Brute force: thu thập tất cả, sort, lấy index

Cách trực tiếp nhất là bỏ qua hoàn toàn cấu trúc BST. Duyệt cây theo bất kỳ thứ tự nào — preorder, postorder, không quan trọng — thu thập tất cả giá trị vào một mảng, sort nó, trả về values[k-1].

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        values = []
 
        def collect(node):
            if not node:
                return
            values.append(node.val)
            collect(node.left)
            collect(node.right)
 
        collect(root)
        values.sort()
        return values[k - 1]

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        var values = new List<int>();
        Collect(root, values);
        values.Sort();
        return values[k - 1];
    }
 
    private void Collect(TreeNode node, List<int> values) {
        if (node == null) return;
        values.Add(node.val);
        Collect(node.left, values);
        Collect(node.right, values);
    }
}

Time: O(n log n) — duyệt cây O(n), sort O(n log n). Space: O(n) để lưu mảng values cộng O(h) cho call stack, trong đó h là chiều cao cây.

Nó hoạt động. Nó đúng. Nhưng nó bỏ qua sự thật hữu ích nhất về input: BST invariant đã cho bạn thứ tự sắp xếp miễn phí. Sort một collection đã được sắp xếp ngầm là lãng phí thuần túy.

Recursive in-order với early termination

In-order traversal visit left subtree, node hiện tại, right subtree. Trên BST, "left subtree rồi node hiện tại rồi right subtree" có nghĩa là "tất cả giá trị nhỏ hơn, rồi giá trị này, rồi tất cả giá trị lớn hơn." Chạy đệ quy từ root và các node xuất hiện theo thứ tự đã sắp xếp.

Phần early termination là điều khiến cách này tốt hơn brute force. Một khi count chạm k, bạn đã tìm được đáp án và không bao giờ cần visit thêm node nào. Với k nhỏ trên cây lớn cân bằng — chẳng hạn k=1 trên cây 10^4 node — bạn dừng sau khi visit O(log n) node dọc theo left spine, rồi thêm một node nữa. Không có lý do gì để chạm vào 9999 node còn lại.

Trace qua ví dụ 2 từng bước. Call tree đi xuống left từ 5 đến 3 đến 2 đến 1. Node 1 không có left child, nên chúng ta xử lý nó trước: count thành 1. Quay lại node 2: count thành 2. Quay lại node 3 — left subtree xong, xử lý node 3: count thành 3, bằng k. Lưu kết quả, return ngay. Right subtree của 3 và 5, cộng node 6, không bao giờ được visit.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.count = 0
        self.result = 0
 
        def inorder(node):
            if not node or self.count >= k:
                return
            inorder(node.left)
            self.count += 1
            if self.count == k:
                self.result = node.val
                return
            inorder(node.right)
 
        inorder(root)
        return self.result

public class Solution {
    private int _count = 0;
    private int _result = 0;
 
    public int KthSmallest(TreeNode root, int k) {
        _count = 0;
        _result = 0;
        InOrder(root, k);
        return _result;
    }
 
    private void InOrder(TreeNode node, int k) {
        if (node == null || _count >= k) return;
        InOrder(node.left, k);
        _count++;
        if (_count == k) {
            _result = node.val;
            return;
        }
        InOrder(node.right, k);
    }
}

Time: O(h + k) trong đó h là chiều cao cây. Trên cây cân bằng là O(log n + k); trên cây lệch hoàn toàn (mỗi node chỉ có right child) xuống thành O(n). Space: O(h) cho recursion stack — O(log n) khi cân bằng, O(n) worst case.

Guard self.count >= k ở đầu inorder là early termination. Nếu không có nó, recursion tiếp tục vào right subtree sau khi đáp án đã tìm được. Cả hai nhánh của mỗi inorder call đều kiểm tra điều kiện này, nên khi count chạm k toàn bộ recursion dừng gọn gàng.

Iterative in-order: cùng logic, stack tường minh

Phiên bản iterative tái tạo recursion call stack thủ công bằng Python list hoặc C# Stack<T>. Logic giống hệt — đi xuống left càng sâu càng tốt, xử lý node hiện tại, chuyển sang right — nhưng control flow là một vòng lặp tường minh thay vì recursive calls.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        current = root
        count = 0
 
        while stack or current:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            count += 1
            if count == k:
                return current.val
            current = current.right
 
        return -1  # không thể đến đây với input hợp lệ

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        var stack = new Stack<TreeNode>();
        var current = root;
        int count = 0;
 
        while (stack.Count > 0 || current != null) {
            while (current != null) {
                stack.Push(current);
                current = current.left;
            }
            current = stack.Pop();
            count++;
            if (count == k) return current.val;
            current = current.right;
        }
 
        return -1; // không thể đến đây với input hợp lệ
    }
}

Inner while current loop đi xuống node ngoài cùng bên trái chưa được visit và push tất cả dọc đường lên stack. Khi vòng lặp đó kết thúc, stack.pop() trả cho bạn node tiếp theo theo in-order — bạn xử lý nó, tăng count, rồi chuyển sang right child của nó (trở thành current mới cho iteration tiếp theo của outer loop).

Time và space giống phiên bản recursive — O(h + k) time, O(h) stack space — vì explicit stack giữ chính xác những gì call stack giữ trong phiên bản recursive.

Các edge case

k=1 (phần tử nhỏ nhất). Thuật toán đi xuống toàn bộ left spine đến node minimum và dừng ngay tại lần kiểm tra count == k đầu tiên. Không vấn đề gì.

k=n (phần tử lớn nhất). In-order traversal visit mọi node; đến lần visit thứ n count chạm k và return. Đây là worst case cho early termination — bạn phải trả đủ chi phí O(n). Đó cũng chính xác là những gì brute force tốn (trừ phần sort), nên không approach nào có lợi thế ở đây.

Cây một node, k=1. Root không có left child. Inner descent bỏ qua ngay, xử lý root, count=1=k, trả về root.val. Đúng.

Cây lệch hoàn toàn về trái (như linked list đi trái). h=n. Cả recursive lẫn iterative đều dùng O(n) stack space. Không có vấn đề về correctness, nhưng đây là degenerate case. Ở n=10^4 vẫn ổn; ở n=10^5 bạn bắt đầu lo về Python's default recursion limit (thường là 1000). Iterative version xử lý điều đó mà không gặp vấn đề.

Tất cả giá trị giống nhau. BST invariant cho phép duplicates ở left child tùy implementation. In-order vẫn visit chúng theo thứ tự left-root-right; lần visit thứ k vẫn return sau k lần tăng count. Đúng.

So sánh complexity

Follow-up: query nhiều lần trên BST thay đổi thường xuyên

Bài toán hỏi bạn làm gì nếu BST bị modify thường xuyên — insert và delete — và kthSmallest được gọi nhiều lần. Đáp án là augment mỗi node với kích thước subtree của nó.

Mỗi node lưu thêm một field: size = 1 + left.size + right.size (leaf node có size 1). Khi insert hoặc delete, bạn cập nhật các size field dọc đường lên root. Với thông tin đó, kthSmallest trở thành binary search trên subtree sizes:

• Nếu k <= left.size, đáp án nằm trong left subtree — đệ quy sang trái với cùng k.
• Nếu k == left.size + 1, node hiện tại chính là phần tử nhỏ thứ k — trả về nó.
• Còn lại, đáp án nằm trong right subtree — đệ quy sang phải với k - left.size - 1.

class TreeNodeWithSize:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.size = 1
 
class AugmentedSolution:
    def kthSmallest(self, root: TreeNodeWithSize, k: int) -> int:
        left_size = root.left.size if root.left else 0
        if k <= left_size:
            return self.kthSmallest(root.left, k)
        elif k == left_size + 1:
            return root.val
        else:
            return self.kthSmallest(root.right, k - left_size - 1)

Query giảm xuống O(h) — không còn O(h + k). Trên balanced BST là O(log n) mỗi query. Insert và delete vẫn tốn O(h) vì bạn cập nhật size trên đường quay lên. Nếu BST là self-balancing (AVL, red-black), cả hai thao tác đều đạt O(log n).

Tôi sẽ dùng augmented version ngay khi "query nhiều lần" xuất hiện trong requirements. Overhead mỗi insert/delete chỉ là một lần cập nhật integer cho mỗi node trên path — không đáng kể — còn speedup cho query thì đáng kể với k lớn trên cây sâu.

Phiên bản nào để dùng thực tế

Với single query trên cây tĩnh, recursive in-order là lựa chọn đầu tiên của tôi. Nó ngắn hơn, early-termination logic rõ ràng, và stack overflow không phải lo thực sự ở n=10^4. Tôi chỉ chuyển sang iterative khi ngôn ngữ đặt recursion limit chặt và cây bị lệch.

Với query nhiều lần trên cây thay đổi, augment node structure. In-order approach trở nên tốn kém không cần thiết khi gọi hàng trăm lần — mỗi call tốn O(h + k) mà size field có thể giảm xuống O(h).

Brute force thì tốt để prototype hoặc khi bạn đã có values được thu thập vì lý do khác. Không phải thứ tôi sẽ commit.

Vị trí trong series và các bài tương tự

Trong trees series, các bài trước (invert binary tree, maximum depth, same tree) thiết lập pattern đi bộ qua cây đệ quy cơ bản. Level-order traversal giới thiệu BFS. Bài này là bài đầu tiên mà loại của cây — BST thay vì generic binary tree — thay đổi thuật toán. In-order trên cây nhị phân ngẫu nhiên không cho bạn điều gì hữu ích; trên BST nó trao cho bạn các giá trị theo thứ tự sắp xếp.

Các bài cùng pattern: LeetCode 94 (binary tree inorder traversal) là nền tảng — luyện tập đó trước nếu in-order traversal còn lạ lẫm. LeetCode 98 (validate BST) cũng khai thác in-order, kiểm tra sequence là strictly increasing. LeetCode 173 (BST iterator) thực chất là in-order iterative approach được đóng gói thành class với next() và hasNext() — explicit stack version từ approach 3 map trực tiếp vào design đó. LeetCode 285 (inorder successor in BST) hỏi về node tiếp theo theo in-order, là một mở rộng nhỏ: thay vì đếm đến k bạn đi cho đến khi tìm thấy giá trị lớn hơn kế tiếp.