A Common-Sense Guide to Data Structures and Algorithms

Deletion

Deletion is the least straightforward operation within a binary tree, and requires some careful maneuvering. Let’s say that we want to delete the 4 from this binary tree:

First, we perform a search to first find the 4, and then we can just delete it one step:

While that was simple, let’s say we now want to delete the 10 as well. If we delete the 10

we end up with an 11 that isn’t connected to the tree anymore. And we can’t have that, because ...