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 ...

Get A Common-Sense Guide to Data Structures and Algorithms now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.