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

Đáp án đúng: "35, 20, 45, 10, 25, 40, 22, 30". Cây ban đầu có gốc 35, con trái 20 với hai con 10 và 30, nút 30 có con trái 25, nút 45 có con trái 40. Chèn 22: nhỏ hơn 35 nên sang trái, lớn hơn 20 nên sang phải tới 30, nhỏ hơn 30 nên tới 25, nhỏ hơn 25 nên thành con trái của 25. Khi đó nút 30 có nhánh trái cao hai mức và nhánh phải rỗng nên chênh 2, đây là nút mất cân bằng thấp nhất và thuộc dạng trái–trái, chữa bằng một phép quay phải tại 30: nút 25 lên thay chỗ, giữ 22 làm con trái và nhận 30 làm con phải. Cây thành gốc 35 với 20 và 45, dưới 20 là 10 và 25, dưới 25 là 22 và 30, dưới 45 là 40. "35, 20, 45, 10, 30, 40, 25, 22" là trạng thái nếu không quay gì cả, khi đó cây không còn thoả điều kiện AVL. "35, 20, 45, 10, 25, 40, 30, 22" đặt 30 làm con trái và 22 làm con phải của 25, ngược thứ tự khoá. "35, 20, 45, 10, 40, 25, 22, 30" đọc 40 trước 25 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.