In the picture how would node with key 2 be deleted from an AVL tree? The rule I know is replace it with the right subtree's left most child, but but 3 doesn't have a left child. I can't replace 2 with 4 b/c 3<4 so do I replace 2 with 3?
![]()
In the picture how would node with key 2 be deleted from an AVL tree? The rule I know is replace it with the right subtree's left most child, but but 3 doesn't have a left child. I can't replace 2 with 4 b/c 3<4 so do I replace 2 with 3?
![]()
The right subtree's left-most child is not quite accurate. It's actually the smallest node in the right subtree. A completely valid alternative is the largest node in the left subtree. The smallest node in the right subtree is the right subtree's root, i.e. the 3 node.
Thanks