Searching

Here, again, is a binary search tree:

The algorithm for searching within a binary search tree is as follows:

1. Designate a node to be the current node. (At the beginning of the algorithm, the root node is the first current node.)

2. Inspect the value at the current node.

3. If we’ve found the value we’re looking for, great!

4. If the value we’re looking for is less than the current node, search for it in its left subtree.

5. If the value we’re looking for is greater than the current node, search for it in its right subtree.

6. Repeat Steps 1 through 5 until we find the value we’re searching for, or until we hit the bottom of the tree, in which case our value must not be in the tree.

Say we want to search for the 61. Let’s see how many steps it would take, by walking through this visually.

When searching through a tree, we must always begin at the root:

Next, the computer asks itself: is the number we’re searching for (61) greater or less than the value of this node? If the number we’re looking for is less than the current node, look for it in the left child. If it’s greater than the current node, look for it in the right child.

In this example, because 61 is greater than 50, we know it must be somewhere to the right, so we search the right child. In the following picture, we’ve shaded out all the nodes we’ve eliminated from our search, since we know that the 61 cannot possibly be there:

“Are you my mother?” asks the algorithm. Since the 75 is not the 61 we’re looking for, we need to move down to the next level. And because 61 is less than 75, we’ll check the left child, since the 61 could only be in that subtree, as shown in the .

The 56 is not the 61 we’re looking for, so we continue our search. Since 61 is greater than 56, we search for the 61 in the right child of the 56:

We found it! In this example, it took us four steps to find our desired value.

The Efficiency of Searching a Binary Search Tree

If you take another look at the steps we just walked through, you’ll notice that each step eliminates half of the remaining nodes from our search. For example, when we begin our search, we start at the root node, and our desired value may be found among any of the root’s descendants. However, when we then decide to continue the search with, say, the root’s right child, we eliminate the left child and all of its descendants from the search.

We’d say, then, that searching in a binary search tree is O(log N), which is the apt description for any algorithm that eliminates half of the remaining values with each step. (We’ll see soon, though, that this is only for a perfectly balanced binary search tree, which is a best-case scenario.)

Log(N) Levels

Here’s yet another way of describing why search in a binary search tree is O(log N), which will reveal another property about binary trees in general: if there are N nodes in a balanced binary tree, there will be about log N levels (that is, rows).

To understand this, let’s assume each row in the tree is completely filled with nodes, and that there aren’t any empty positions. If you think about it, each time we add a new full level to the tree, we end up roughly doubling the number of nodes that the tree has. (Really, we’re doubling the nodes and adding one.)

For example, a binary tree with four complete levels has fifteen nodes. (Go ahead, count them.) If we add a fifth complete level, that means we add two children to each of the eight nodes in the fourth level. This means we add sixteen new nodes, roughly doubling the size of the tree.

It emerges that each new level doubles the size of the tree. Accordingly, a tree containing N nodes will require log(N) levels to hold all the nodes.

In the context of binary search, we noted that the pattern of log(N) is that with each step of the search, we can eliminate half of the remaining data. The number of levels needed in a binary tree follows this pattern as well.

Let’s take a binary tree that needs to hold thirty-one nodes. With our fifth level, we can hold sixteen of those nodes. This took care of roughly half of the data, leaving us with just fifteen nodes that we still need to find room for. With the fourth level, we take care of eight of those nodes, leaving us with seven unaccounted for. With the third level, we take care of four of those nodes, and so on.

Indeed, log 31 is (approximately) 5. So we’ve now concluded that a balanced tree with N nodes will have log(N) levels.

Since this is the case, it makes a lot of sense as to why searching a binary search tree takes up to log(N) steps: because each step of the search causes us to move down a level, we take up to as many steps as there are levels in the tree.

However you prefer to think about it, searching a binary search tree takes O(log N).

Now, while search in a binary search tree is O(log N), so is binary search within an ordered array, in which each number we select also eliminates half of the remaining possible values. In this regard, then, searching a binary search tree has the same efficiency as binary search within an ordered array.

Where binary search trees really shine over ordered arrays, though, is with insertion. We’ll get to that soon.

Code Implementation: Searching a Binary Search Tree

To implement the search operation, as well as the other binary search tree operations, we’re going to make heavy use of recursion. You learned back in Chapter 10, , that recursion is key when dealing with data structures that have an arbitrary number of levels of depth. A tree is such a data structure, as it can have an infinite number of levels.

Here’s how we can use recursion to implement search with Python. While we could have alternatively used a loop instead, the recursive code for search is more concise and elegant:

This search function accepts the search_value we’re searching for and a node that we’ll use as the base for our search. The first time we call search, the node will be the root node. However, in the subsequent recursive calls, the node may be another node within the tree.

Our function deals with four possible cases, two of which are the base cases:

One base case is when the node contains the search_value we’re looking for, in which case we can return the node and not make any recursive calls.

The other base case is when there is no node. This will make more sense after we’ve examined the other cases, so let’s come back to this shortly.

The next case is when the search_value is less than the value of the current node:

In this case, we know that if it exists in the tree, the search_value will have to be found somewhere among this node’s left descendants. So we recursively call the search function on this node’s left child.

The next case is the inverse; it’s when the search_value is greater than the current node:

In this case, we recursively call search on the current node’s right child.

Now, when we make these recursive calls on the current node’s children, note that we didn’t check whether the current node even has any children. That’s where the first base case comes in:

That is to say, if it turns out that we called search on a child node that doesn’t actually exist, we end up returning None (since the node variable will actually contain None). This case will happen if the search_value doesn’t exist within our tree, as we’ll try to access the node where the search_value should be found, but our search hits a dead end. In this case, it’s appropriate that we return None, indicating that the search_value is not within the tree.