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, 45, 12, 27, 40, 24, 32". Cây ban đầu: gốc 35, con trái 22 với hai con 12 và 32, nút 32 có con trái 27, nút 45 có con trái 40. Chèn 24: nhỏ hơn 35 nên sang trái, lớn hơn 22 nên sang phải tới 32, nhỏ hơn 32 nên tới 27, nhỏ hơn 27 nên thành con trái của 27. Khi đó nút 32 có nhánh trái cao hai mức và nhánh phải rỗng nên chênh 2; đó là nút mất cân bằng thấp nhất, dạng trái–trái, chữa bằng một phép quay phải tại 32: nút 27 lên thay chỗ, 24 vẫn là con trái của 27 và 32 thành con phải. Cây thành gốc 35 với 22 và 45, dưới 22 là 12 và 27, dưới 27 là 24 và 32, dưới 45 là 40. "35, 22, 45, 12, 32, 40, 27, 24" là trạng thái khi không quay, lúc đó cây vi phạm điều kiện AVL tại 32. "35, 22, 45, 12, 32, 40, 24, 27" cũng giữ 32 ở mức ba, chỉ đổi thứ tự hai nút mức bốn. "35, 22, 45, 12, 40, 27, 24, 32" đọc 40 trước 27 trong cùng mức ba, trái với chiều từ trái sang phải của duyệt theo mức.