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

Đáp án đúng: "35, 22, 39, 12, 28, 37, 27, 32". Cây có gốc 35, nhánh trái 22 với hai con 12 và 32, dưới 32 là con trái 27, nhánh phải 39 với con trái 37. Khoá 28 đi từ 35 sang trái, từ 22 sang phải, từ 32 sang trái, từ 27 sang phải nên thành con phải của 27. Lúc đó nút 32 có nhánh trái cao 2 và nhánh phải rỗng, lệch 2, điểm chèn lại nằm ở nhánh phải của con trái nên là ca trái phải: quay 27 sang trái rồi quay 32 sang phải, kết quả 28 lên làm gốc đoạn với 27 bên trái và 32 bên phải. Duyệt theo chiều rộng cho 35, rồi 22 và 39, rồi 12, 28, 37, rồi 27 và 32. Dãy "35, 22, 39, 12, 32, 37, 27, 28" là trạng thái khi chưa quay, vẫn để 32 lệch 2 nên không còn là cây AVL. Dãy "35, 22, 39, 12, 32, 37, 28, 27" giữ 32 làm gốc đoạn và đặt 28 bên trái 27, phá thứ tự tìm kiếm vì 27 nhỏ hơn 28. Dãy "35, 22, 39, 12, 37, 28, 27, 32" xếp 37 trước 28 ở cùng mức, nhưng duyệt chiều rộng đọc nhánh trái trước nên 28 nằm dưới 22 phải đứng trước 37 nằm dưới 39.