How do we delete a node from an AVL tree, or just a binary search tree, in general? Note that the node being delete does not need to be a leaf.
Let us consider the following tree: (TLnTR). When node n is “deleted”, its value can be replaced by that of the rightmost node of TL or that of the leftmost node of TR. After the value replacement, the “donor” node can be deleted.
However, this donor node may not be a leaf, either. Consequently, the node swap operation may propagate. This can be done recursively.