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:

images/chapter13/binary_trees_Part6.png

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

images/chapter13/binary_trees_Part16.png

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

images/chapter13/binary_trees_Part17.png

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.