Trong bài toán xử lý cây phân cấp nhân sự hoặc danh mục sản phẩm (Category Tree) tại các hệ thống thương mại điện tử lớn, làm thế nào để tính khoảng cách ngắn nhất (độ dài đường đi) giữa hai nút bất kỳ trong một Binary Tree một cách hiệu quả?

Question

Accepted Answer

Khoảng cách ngắn nhất giữa hai nút A và B trong một Binary Tree chính là tổng số cạnh trên đường đi từ A đến B. Bài toán này có thể giải quyết thông qua việc tìm nút cha chung gần nhất (Lowest Common Ancestor - LCA).
Phân tích giải thuật
Khoảng cách từ nút gốc (Root) đến bất kỳ nút nào được tính bằng chiều dài đường đi từ Root đến nút đó. Khoảng cách giữa hai nút p và q được tính bằng công thức:
Distance(p, q) = Distance(Root, p) + Distance(Root, q) - 2 * Distance(Root, LCA(p, q))
Các bước thực hiện

Tìm nút LCA của p và q bằng thuật toán đệ quy DFS.
Tính chiều cao hoặc khoảng cách từ LCA đến p.
Tính chiều cao hoặc khoảng cách từ LCA đến q.
Tổng hai khoảng cách trên chính là khoảng cách ngắn nhất giữa hai nút.

Lưu ý tối ưu trong Enterprise
Nếu hệ thống thường xuyên phải truy vấn khoảng cách hoặc quan hệ cha-con trong cây danh mục tĩnh, việc sử dụng kỹ thuật Binary Lifting (Sparse Table) hoặc Euler Tour Technique kết hợp RMQ (Range Minimum Query) sẽ giúp giảm độ phức tạp thời gian truy vấn xuống O(1) sau bước tiền xử lý O(N log 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 binary tree liên quan cùng chủ đề