Kth Smallest Element in a BST

Bài toán

Cho root của một BST và số nguyên k. Tìm giá trị của phần tử nhỏ thứ k (1-indexed) trong cây.

Phân Tích & Tiếp Cận

Tính chất In-order Traversal

Duyệt In-order (Left -> Root -> Right) trên một cây BST sẽ luôn cho ra một dãy số đã sắp xếp tăng dần. Ví dụ cây [3, 1, 4, null, 2]. In-order: 1, 2, 3, 4. Phần tử nhỏ thứ k chính là phần tử thứ k trong quá trình duyệt này.

Cách 1: Recursive (Dễ hiểu)

Duyệt hết cây -> Lưu vào mảng -> Trả về arr[k-1]. Nhược điểm: Phải duyệt và lưu hết cây ($O(n)$ space). Nếu $k=1$, ta vẫn duyệt hết cây.

Cách 2: Iterative Stack (Tối ưu)

Ta có thể dừng ngay lập tức khi đếm đủ k phần tử.

function kthSmallest(root: TreeNode | null, k: number): number {
    const stack: TreeNode[] = [];
    let curr = root;

    while (curr || stack.length > 0) {
        // 1. Đi sang trái tận cùng
        while (curr) {
            stack.push(curr);
            curr = curr.left;
        }

        // 2. Pop node (đây là node nhỏ nhất hiện tại)
        curr = stack.pop()!;
        k--; // Đánh dấu đã tìm thấy thêm 1 số nhỏ

        if (k === 0) {
            return curr.val;
        }

        // 3. Đi sang phải
        curr = curr.right;
    }
    
    return -1; // Should not reach here
}

• Time Complexity: $O(H + k)$. Ta đi xuống độ sâu H để tìm min, sau đó pop k lần. Tốt hơn O(N) nếu k nhỏ.
• Space Complexity: $O(H)$ (cho stack).

Pattern Nhận Diện

Khi cần tìm thứ tự, hạng (Rank), hoặc sort trong BST -> In-order Traversal.