What is the result of the breadth first traverse of the binary search tree T, after inserting the following keys into the tree sequentially (suppose T is empty before insertion): 16, 7, 3, 1, 12, 20, 17

Đáp án đúng: "16, 7, 20, 3, 12, 17, 1". Chèn lần lượt vào cây tìm kiếm rỗng: 16 thành gốc; 7 nhỏ hơn 16 nên thành con trái của 16; 3 nhỏ hơn 16 rồi nhỏ hơn 7 nên thành con trái của 7; 1 nhỏ hơn 3 nên thành con trái của 3; 12 nhỏ hơn 16 nhưng lớn hơn 7 nên thành con phải của 7; 20 lớn hơn 16 nên thành con phải của 16; 17 lớn hơn 16 và nhỏ hơn 20 nên thành con trái của 20. Các mức vì vậy là 16; rồi 7 và 20; rồi 3, 12, 17; rồi 1. Duyệt theo chiều rộng cho 16, 7, 20, 3, 12, 17, 1. Dãy "16, 7, 20, 3, 12, 1, 17" đặt 1 trước 17, nhưng 17 là con của 20 nên nằm ở mức ba còn 1 là con của 3 ở mức bốn. Dãy "16, 7, 20, 3, 17, 1, 12" đẩy 12 xuống mức cuối, dù 12 là con phải của 7 nên cùng mức với 3 và 17. Dãy "16, 7, 20, 3, 17, 12, 1" cũng đưa 12 khỏi mức ba và còn xếp nó sau 17, trong khi mức ba đọc từ trái sang phải là 3, 12 rồi 17.