2-3 Deletion (Case #1)

This lesson will cover the deletion operation in 2-3 trees, discussing all the four scenarios based on the position of the element which needs to be deleted.

Deletion Algorithm:

Deletion in 2-3 Trees is implemented based on the same scenarios we discussed in the last lesson but in the reverse order. The deletion algorithm also takes O(Logn)O(Logn) time. And, just like insertion, deletion also begins from the leaf node. The deletion in 2-3 Trees is performed based on these scenarios:

Case 1: Element at Leaf:

When the element which needs to be removed is present at the leaf node, we check how many keys are present in that node; this further divides the algorithm into two scenarios:

1.1 Leaf node has more than one key:

If the leaf at which the element to be deleted has more than one key, then simply delete the element.

Example: See the following example where the node has more than one key.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.