A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Insertion

As I mentioned earlier, binary search trees are at their best when it comes to insertion. Now we’ll see why.

Say we want to insert the number 45 into our example tree. The first thing we’d have to do is find the correct node to attach the 45 to. To begin our search, we start at the root:

Since 45 is less than 50, we drill down to the left child:

Since 45 is greater than 25, we must inspect the right child:

Since 45 is greater than 33, we ...