A Common-Sense Guide to Data Structures and Algorithms

Insertion

To discover the algorithm for inserting a new value into a binary tree, let’s work with an example. Say that we want to insert the number 45 into the previous 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:

45 is greater than 33, so we check ...