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 check the 33’s right child:

At this point, we’ve reached a node that has no children, so we have nowhere to go. This means we’re ready to perform our insertion.

Since 45 is greater than 40, we insert it as a right child of the 40:

In this example, insertion took five steps, consisting of four search steps plus one insertion step. Insertion always takes just one extra step beyond a search, which means insertion takes (log N) + 1 steps. In Big O notation, which ignores constants, this is O(log N).

In an ordered array, by contrast, insertion takes O(N), because in addition to search, we must shift a lot of data to the right to make room for the value we’re inserting.

This is what makes binary search trees so efficient. While ordered arrays have O(log N) search and O(N) insertion, binary search trees have O(log N) search and O(log N) insertion. This becomes critical in an application in which you anticipate a lot of changes to your data.

Code Implementation: Binary Search Tree Insertion

Here’s a Python implementation of inserting a new value into a binary search tree. Like the search function, it’s recursive:

The insert function accepts a value that we’re going to insert and a node that serves as the ancestor node for which our value will become a descendant.

First, we check whether the value is less than the value of the current node:

If the value is less than the node, we know that we need to insert the value somewhere among the left descendants of the node.

We then check to see whether the current node has a left child. If the node doesn’t have a left child, we make the value into the left child, since that’s exactly where the value belongs:

This is the base case, since we don’t need to make any recursive calls.

However, if the node already has a left child, we can’t place the value there. Instead, we recursively call insert on the left child so that we continue to search for the spot in which we’ll place the value:

Eventually, we’ll hit a descendant node that doesn’t have its own child, and that’s where the value is going to go.

The rest of the function is the exact inverse; it handles cases where the value is greater than the current node.

The Order of Insertion

It’s important to note that only when creating a tree out of randomly sorted data do trees usually wind up being well-balanced. However, if we insert sorted data into a tree, it can become imbalanced and less efficient. For example, if we were to insert the following data in this order—1, 2, 3, 4, 5—we’d end up with a tree that looks like this:

This tree is completely linear, so searching for the 5 within this tree would take O(N).

However, if we inserted the same data in the following order—3, 2, 4, 1, 5—the tree would be evenly balanced:

Only with a balanced tree does search take O(log N).

Because of this, if you ever want to convert an ordered array into a binary search tree, you’d want to first randomize the order of the data.

It emerges that in a worst-case scenario, when a tree is completely imbalanced, search is O(N). In a best-case scenario, when it is perfectly balanced, search is O(log N). In the typical scenario, in which data is inserted in random order, a tree will be pretty well balanced and search will take about O(log N).