--- title: "AVL delete then insert gives same tree?" subject: "Data Structure and Algorithm" chapter: 6 key: "semester_4/data_structure_and_algorithm:avl-delete-insert-original" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/avl-delete-insert-original site: BCT Engineering --- # AVL delete then insert gives same tree? Data Structure and Algorithm · Chapter 6: Trees - Asked in: 2069 Poush, 4 marks - Video: [5.15 AVL Tree Deletion in Data structures | with Example | DSA Tutorials](https://www.youtube.com/watch?v=LXdi_4kSd1o) — Jenny's Lectures CS IT - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/avl-delete-insert-original - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6 ## Question If you delete a node from an AVL tree and insert it back again, will you always get the original tree back? Illustrate with example. ## Short answer No, deleting and reinserting a node does not always restore the original AVL tree because rotations during deletion may not be undone by insertion. For example, deleting 10 from a tree with root 20 triggers a left rotation, making 30 the root; reinserting 10 does not rotate back, leaving root 30. ## Answer **No.** Deleting a node and inserting the same key back does not always give the original AVL tree. The reason is that deletion and insertion may each trigger rotations, and the rotation done during the deletion is not undone by the one (if any) done during insertion. The shape of an AVL tree depends on the order of operations, not only on the set of keys. #### Example Start with this AVL tree (built by inserting 20, 10, 30, 25, 40): ```text 20 / \ 10 30 / \ 25 40 ``` **Delete 10.** Node 20 now has left height 0 and right height 2, so bf = −2. Its right child 30 has bf = 0, which is a right-heavy case, so a single left rotation at 20 is done: ```text 30 / \ 20 40 \ 25 ``` **Insert 10 again.** It goes to the left of 20. Node 20 now has bf = 0 and node 30 has bf = +1, so no node reaches ±2 and no rotation happens: ```text 30 / \ 20 40 / \ 10 25 ``` The final tree has root 30, whereas the original had root 20. Both are valid AVL trees with the same keys, but they differ. Only if the deletion needed no rotation (for example removing a leaf that keeps all balance factors in range) is the original tree restored. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Will deleting a node and inserting it back always give the original AVL tree? A. Yes, always B. Yes, but only for leaf nodes C. No, not always D. Yes, if the keys are inserted in sorted order Answer: C. The shape depends on the order of operations. Rotations in the deletion are not undone by insertion. (Key point: Main result) 2. Why can the original tree fail to return? A. The deletion may cause a rotation, and the insertion need not cause the reverse rotation B. Insertion never causes rotations C. AVL trees ignore duplicate keys D. The deleted key is lost from memory Answer: A. Rotation done during deletion changes the shape; reinserting the key may need no rotation, so the new shape stays. (Key point: Reason) 3. In the example, deleting 10 from the tree with root 20 causes what? A. Node 20 gets bf = +2 and a right rotation is done B. No imbalance; the tree is unchanged C. Node 20 gets bf = -2 and a single left rotation at 20 makes 30 the root D. A double rotation at 30 Answer: C. After removing 10, 20 has left height 0 and right height 2, and its right child 30 has bf 0, so a single left rotation is used. (Key point: Example deletion) 4. When will the original tree be restored? A. When the deletion needed no rotation (e.g. removing a leaf that keeps all balance factors in range) B. Only when the deleted node was the root C. Whenever the tree has fewer than 5 nodes D. When the key is inserted twice Answer: A. If no rotation was done by the deletion, reinserting the key at the same place restores the original shape. (Key point: When original returns) ## Related in Data Structure and Algorithm - [Insert and delete kth node in doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adoubly-insert-delete-kth) — Data Structure and Algorithm, chapter 4, asked 2× - [Insert and delete before a node, singly linked](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asingly-insert-delete-before) — Data Structure and Algorithm, chapter 4 - [Delete last node of doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adelete-end-node-doubly) — Data Structure and Algorithm, chapter 4 - [Insert before Kth node in doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adoubly-insert-before-kth) — Data Structure and Algorithm, chapter 4 - [AVL tree for month names](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-months) — Data Structure and Algorithm, chapter 6, asked 2× - [B-tree insertion algorithm; AVL of months](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-insertion-avl-months) — Data Structure and Algorithm, chapter 6, asked 2×