2-3 Deletion (Case #2)

How do you delete an element present at an internal node? This lesson provides an answer with the help of an example.

We'll cover the following

Case 2: Element at internal node

Deletion is always performed at the leaf. Whenever you need to delete a key at the internal node, swap it with any of its in-order successors, and somehow make it shift to any leaf node as deletion is always performed at the leaf. Shift the element at the leaf node and then delete it. The element to be deleted can be swapped by:

  • An element with the largest key on the left
  • An element with the smallest key on the right

This is applicable when the child node has more than one key stored at the node. If there is only one value at the child node, then you are bound to swap the parent with whatever value the child node has.

Example

See the following illustration, which covers the two scenarios that were discussed above:

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