Skip to main content

AVL delete then insert gives same tree?

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.

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.

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):

        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:

        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:

        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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 6 questions →