Suppose the binary search tree T is made by inserting the following keys consequently: 6, 7, 8, 9, 3, 2, 5, 4 What is the result of breadth-first traverse of T?

Đáp án đúng: "6, 3, 7, 2, 5, 8, 4, 9". Chèn lần lượt 6, 7, 8, 9, 3, 2, 5, 4 vào cây tìm kiếm rỗng cho cây: 6 là gốc, 7 là con phải của 6, 8 là con phải của 7, 9 là con phải của 8, 3 là con trái của 6, 2 là con trái của 3, 5 là con phải của 3, còn 4 nhỏ hơn 5 nên thành con trái của 5. Duyệt theo chiều rộng đọc từng mức từ trên xuống, trong mỗi mức đi từ trái sang phải: mức một có 6, mức hai có 3 và 7, mức ba có 2, 5 và 8, mức bốn có 4 và 9. "6, 7, 8, 9, 3, 2, 5, 4" chỉ là thứ tự chèn, nó vét hết nhánh phải trước khi chạm nhánh trái nên không phải đọc theo mức. "6, 3, 2, 7, 5, 8, 4, 9" đặt 2 ngay sau 3, tức xuống mức ba khi mức hai chưa đọc hết nút 7. "6, 5, 7, 2, 3, 8, 4, 9" coi 5 là con trái của 6, nhưng 5 lớn hơn 3 nên khi chèn nó phải rẽ phải tại nút 3 và nằm ở mức ba.