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 80+ hands-on prep courses.