A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Deletion

Deletion is the least straightforward operation within a binary search tree and requires some careful maneuvering.

Let’s say we want to delete the 4 from this binary search tree:

First, we perform a search to find the 4. We won’t visualize this search again, since you’ve already got that down.

Once we find the 4, we can delete it one step:

Well, that was simple. But let’s see what happens when we try to delete the 10:

We end up with an 11 ...