Binary Search Tree Traversal

Now, we’ve already seen how to search, insert, and delete data from a binary search tree. I mentioned, though, that we also want to be able to print the entire list of book titles in alphabetical order. How can we do that?

First, we need the ability to visit every single node in the tree. Visiting nodes is another term for accessing them. The process of visiting every node in a data structure is known as traversing the data structure.

Second, we need to make sure we traverse the tree in alphabetically ascending order so that we can print the list in that order. You can traverse a tree in multiple ways, but for this application, we’ll perform what is known as inorder traversal, so that we can print each title in alphabetical order.

Recursion is a great tool for performing traversal. We’ll create a recursive function called traverse that can be called on a particular node. The function then performs the following steps:

1. Call itself (traverse) recursively on the node’s left child. The function will keep getting called until we hit a node that does not have a left child.

2. Visit the node. (For our book title app, we print the value of the node at this step.)

3. Call itself (traverse) recursively on the node’s right child. The function will keep getting called until we hit a node that does not have a right child.

For this recursive algorithm, the base case is when we call traverse on a child that does not exist, in which case we return without doing anything further.

Here’s a Python traverse_and_print function that works for our list of book titles. Note how concise it is:

Let’s walk through the inorder traversal step by step.

We first call traverse_and_print on “Moby Dick”. This, in turn, calls traverse_and_print on the left child of “Moby Dick”, which is “Great Expectations”:

Before we move on to that, though, we’re going to add to the call stack the fact that we’re in the middle of the function in “Moby Dick” and the fact that we’re in the middle of traversing its left child:

We then proceed with traverse_and_print("Great Expectations"), which calls traverse_and_print on the left child of “Great Expectations”, which is “Alice in Wonderland”.

Let’s add traverse_and_print("Great Expectations") to the call stack before moving on:

The traverse_and_print("Alice in Wonderland") calls traverse_and_print on the left child of “Alice in Wonderland”. However, there isn’t any left child (the base case), so nothing happens. The next line of traverse_and_print is the following:

This line prints "Alice in Wonderland".

Next, the function attempts to traverse_and_print the right child of “Alice in Wonderland”:

However, there’s no right child (the base case), so the function returns without doing anything further.

Since we’ve completed the function traverse_and_print("Alice in Wonderland"), we check the call stack to see where we’re up to in this recursive soup:

Ah, that’s right. We were in the middle of traverse_and_print("Great Expectations"), and we had just completed calling traverse_and_print on its left child. Let’s pop this from the call stack:

And let’s continue. The function next prints "Great Expectations" and then calls traverse_and_print on the right child, which is “Lord of the Flies”. Before moving on to that, though, let’s hold our place within this function in the call stack:

We now execute traverse_and_print("Lord of the Flies"). First, we call traverse_and_print on its left child, but it doesn’t have one. Next, we print “Lord of the Flies”. Finally, we call traverse_and_print on its right child, but that doesn’t exist either, so the function is now done.

We look at our call stack and see that we were in the process of executing traverse_and_print on the right child of “Great Expectations”. We can pop that from the stack and continue as shown in the following diagram:

Now, it just so happens that we’ve also now completed everything we have to do in traverse_and_print("Great Expectations"), so we can go back to the call stack to see what to do next:

We can see that we were in the middle of traverse_and_print of the left child of “Moby Dick”. We can pop that from the call stack (which leaves the stack empty for now) and continue with the next step within traverse_and_print("Moby Dick"), which is to print “Moby Dick”.

Then, we call traverse_and_print on the right child of “Moby Dick”. We’ll add this to the call stack:

For the sake of brevity (although it’s probably too late for that), I’ll let you walk through the rest of the traverse_and_print function from here.

By the time our function has finished executing, we’ll have printed the nodes in this order:

And that’s how we achieve our goal of printing the book titles in alphabetical order. Note that tree traversal is O(N), since by definition, traversal visits all N nodes of the tree.