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

Đáp án đúng: "35, 22, 39, 12, 27, 37, 24, 32". Cây ban đầu có gốc 35, con trái 22 với hai con 12 và 32 (32 chỉ có con trái 27), con phải 39 chỉ có con trái 37. Chèn 24: nhỏ hơn 35 nên sang 22, lớn hơn 22 nên sang 32, nhỏ hơn 32 nên sang 27, nhỏ hơn 27 nên thành con trái của 27. Lúc này nút 32 có cây con trái cao hai tầng và cây con phải rỗng, hệ số cân bằng -2, mất cân bằng kiểu trái-trái vì khoá mới đi trái hai lần liên tiếp; quay phải tại 32 đưa 27 lên thay chỗ, với con trái 24 và con phải 32. Cây thành gốc 35, mức hai là 22 và 39, mức ba là 12, 27, 37, mức bốn là 24 và 32, nên duyệt theo chiều rộng cho 35, 22, 39, 12, 27, 37, 24, 32. "35, 22, 39, 12, 37, 27, 24, 32" đảo 27 với 37 ở mức ba, nhưng 27 thuộc nhánh trái nên phải đọc trước. "35, 22, 39, 12, 32, 37, 27, 24" và "35, 22, 39, 12, 32, 37, 24, 27" đều giữ 32 ở mức ba, tức không quay, và như vậy 32 vẫn mang hệ số cân bằng -2 nên cây không còn là AVL.