Làm thế nào để thực hiện thuật toán Duyệt cây theo thứ tự trước (Pre-order Traversal) mà không dùng đệ quy, và tại sao cách tiếp cận này lại quan trọng đối với các lập trình viên Junior?

Question

Accepted Answer

Bản chất vấn đề
Khi duyệt cây theo thứ tự trước (Pre-order Traversal) bằng đệ quy, hệ thống sẽ sử dụng Call Stack ngầm định. Đối với các lập trình viên cấp độ Junior, việc hiểu cách chuyển đổi từ đệ quy sang vòng lặp sử dụng cấu trúc dữ liệu Stack thủ công giúp nắm vững cơ chế quản lý bộ nhớ và tránh lỗi Stack Overflow khi xử lý cây có độ sâu lớn.
Hướng giải quyết chi tiết
Để duyệt Pre-order (Gốc -> Trái -> Phải) bằng phương pháp lặp:

Sử dụng một Stack để lưu trữ các nút cần duyệt.
Đưa nút gốc vào Stack.
Trong khi Stack chưa rỗng:
Lấy ra nút ở đỉnh Stack (Pop).
Xử lý giá trị của nút đó.
Đưa nút con bên phải vào Stack trước (nếu có).
Đưa nút con bên trái vào Stack sau (nếu có).

Lý do đưa nút phải vào trước là vì Stack hoạt động theo cơ chế Last-In-First-Out (LIFO), nên nút trái cần được lấy ra xử lý trước.
Ví dụ mã nguồn minh họa (JavaScript)
function preorderTraversal(root) {
    if (!root) return [];

const result = [];
    const stack = [root];

while (stack.length > 0) {
        const currentNode = stack.pop();
        result.push(currentNode.val);

// Đẩy con phải vào trước để con trái được xử lý trước
        if (currentNode.right) {
            stack.push(currentNode.right);
        }
        if (currentNode.left) {
            stack.push(currentNode.left);
        }
    }

return result;
}
Độ phức tạp

Độ phức tạp thời gian: O(N) vì mỗi nút được duyệt qua đúng một lần.
Độ phức tạp không gian: O(H) với H là chiều cao của cây, dùng để lưu trữ các nút trong Stack.

Kinh nghiệm thực chiến
Trong phát triển phần mềm thực tế, việc khử đệ quy (Iterative approach) thường được áp dụng khi làm việc với các hệ thống nhúng có bộ nhớ hạn chế hoặc khi cấu trúc cây trong DOM quá sâu, giúp kiểm soát tốt hơn việc phân bổ tài nguyên bộ nhớ.

Làm thế nào để thực hiện thuật toán Duyệt cây theo thứ tự trước (Pre-order Traversal) mà không dùng đệ quy, và tại sao cách tiếp cận này lại quan trọng đối với các lập trình viên Junior?

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi trees liên quan cùng chủ đề