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

Đáp án đúng: "40, 25, 50, 15, 33, 45, 30, 35". Cây ban đầu có gốc 40, con trái 25 với hai con 15 và 35, con trái của 35 là 30, còn 50 có con trái 45. Chèn 33: nhỏ hơn 40 nên sang 25, lớn hơn 25 nên sang 35, nhỏ hơn 35 nên sang 30, lớn hơn 30 nên thành con phải của 30. Lúc này nút 35 có nhánh trái cao 2 và nhánh phải cao 0, lệch 2 nên mất cân bằng; đường chèn đi trái rồi phải nên phải quay kép: quay trái quanh 30 rồi quay phải quanh 35, đưa 33 lên làm gốc nhánh với hai con 30 và 35. Cây thành 40 có hai con 25 và 50; 25 có hai con 15 và 33; 50 có con trái 45. Duyệt theo lớp cho 40; rồi 25, 50; rồi 15, 33, 45; rồi 30, 35. Phương án "40, 25, 50, 15, 30, 45, 33, 35" ứng với quay đơn để 30 lên thay 35. Phương án "40, 25, 50, 15, 35, 45, 30, 33" ứng với không quay gì, giữ 35 tại chỗ và treo 33 dưới 30. Phương án "40, 25, 50, 15, 30, 45, 35, 33" vừa giữ 30 ở lớp hai lại xếp 35 trước 33 ở lớp ba, trong khi sau quay kép lớp ba chỉ còn 30 và 35.