Consider the AVL tree below. What is the breadth first traversal of the tree after inserting a node with value 3?

Đáp án đúng: "6, 2, 7, 1, 4, 8, 3, 5". Chèn 3 theo đường tìm kiếm: 3 nhỏ hơn 6 nên sang trái tới 2, lớn hơn 2 nên sang phải tới 5, nhỏ hơn 5 nên sang trái tới 4, nhỏ hơn 4 nên thành con trái của 4. Lúc này nút 5 có cây con trái cao hai mức gồm 4 và 3 mà không có con phải, hệ số cân bằng bằng 2 nên mất cân bằng; vì điểm chèn nằm ở nhánh trái của con trái nên chỉ cần một phép quay phải tại 5: nút 4 lên thay chỗ, giữ 3 làm con trái và nhận 5 làm con phải, rồi 4 trở thành con phải của 2. Cây sau quay có gốc 6 với hai con 2 và 7; 2 có con 1 và 4; 7 có con phải 8; 4 có con 3 và 5. Duyệt theo bề rộng cho 6, rồi 2 và 7, rồi 1, 4, 8, cuối cùng 3 và 5. "6, 2, 7, 1, 3, 4, 8, 5" sai vì nó đưa 3 lên cùng mức với 4 và 8, trong khi 3 là con của 4. "6, 2, 7, 1, 3, 5, 8, 4" sai vì nó cho 3 lên làm gốc cây con sau phép quay, tức quay quanh nút 4 thay vì quanh nút 5. "6, 2, 7, 1, 5, 8, 3, 4" sai vì đó là cây chưa quay, vẫn để 5 ở mức ba với hệ số cân bằng 2, vi phạm điều kiện AVL.