Given a binary search tree T below. What is a result of breadth-first traverse of T after you delete by merging the node 3?

Đáp án đúng: "6, 1, 8, 2, 7, 4, 5". Cây có gốc 6 với con trái 3 và con phải 8; nút 3 có con trái 1 và con phải 4; nút 1 có con phải 2; nút 4 có con phải 5; nút 8 có con trái 7. Xoá bằng cách trộn là bỏ hẳn nút 3, đưa nhánh trái của nó lên thay chỗ và treo nhánh phải vào nút phải nhất của nhánh trái: nút phải nhất của nhánh 1 là 2, nên nhánh gồm 4 và 5 thành con phải của 2, còn 1 lên làm con trái của 6. Đọc theo mức: 6; rồi 1 và 8; rồi 2 và 7; rồi 4; rồi 5. "6, 2, 8, 1, 4, 7, 5" là kết quả của cách xoá bằng cách thế, tức đưa 2 lên đúng vị trí nút 3 và giữ nguyên hai nhánh, nên 1 và 4 cùng ở mức ba. "6, 2, 7, 1, 4, 8, 5" còn kéo 7 lên mức hai, nhưng 7 là con của 8 nên phải nằm dưới 8. "6, 1, 7, 2, 8, 5, 4" cũng kéo 7 lên mức hai và đẩy 8 xuống mức ba, trong khi phép xoá này không chạm gì tới nhánh phải của gốc.