[SQL] Truy vấn cây nhị phân

Cho bảng BST bao gồm 2 cột N và P: cột N đại diện cho giá trị của node trong cây nhị phân, và P chứa giá trị của node cha của N. Viết câu truy vấn liệt kê ra loại (type) của node trong cây nhị phân theo quy luật như sau:

"Root" - nếu node là root node.

"Leaf" - nếu node là node lá.

"Inner" - nếu không phải 2 trường hợp trên.

Ví dụ bảng BST:

Ví dụ minh họa:

Kết quả:

1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf

Để giải được bài tập này, chúng ta cần sử dụng câu lệnh CASE, tương tự như lệnh switch-case trong các ngôn ngữ lập trình phổ biến. Từ bảng ví dụ ở trên, dễ thấy một node là "Root" nếu P=null, là "Inner" nếu giá trị của N không xuất hiện trong cột P. Dựa vào logic đã được phân tích, ta có đáp án bên dưới:

SELECT N,
CASE
    WHEN P IS NULL THEN "Root"
    WHEN N IN (SELECT DISTINCT P FROM BST) THEN "Inner"
    ELSE "Leaf"
END
FROM BST
ORDER BY N

Bài tập trên được lấy từ trang HackerRank.com với độ khó Medium. Để tìm hiểu nhiều hơn các bài tập khác, các bạn hãy đăng ký một tài khoản trên trang này và kết nối cùng tôi nhé.