Iterating Over Our BST

The iterators we implemented for array-backed lists and linked lists were ultimately pretty simple because those are already ordered structures.

Here, our iterator will have to linearize a nonlinear data structure! So an iterator for a BST will likely require a more complicated encoding and implementation.

There are many possible ways to order the items in a binary tree.

One especially cool ordering actually gives the items of the BST in sorted order!

In-Order Traversal

Say we want to print out every key in a BST in sorted order (i.e., from lowest to highest).

The BST property says that, at any given node, every key in the left subtree is smaller than the node's key, which is smaller than every key in the right subtree.

We can use the same method we used to design a recursive algorithm for insert:

1. Identify precisely what the algorithm will do.
   • What inputs does it take?
   • What results does it promise?
2. Identify the base case.
   • What is the simplest possible input?
   • How do we satisfy the promise in that case?
3. Identify the recursive step. (This is the part that trips a lot of people up!)
   • We know what our algorithm does, right?
     • We decided in Step 1.
   • So let's assume that it really works, but only for inputs "closer" to the base case than the one we have.
     • We carve off a smaller chunk of our problem and use our algorithm on it, relying on the promise we made.
     • Then we take that result and do whatever else we need to do to satisfy the promise for the input we were given.
4. Double check: Does our algorithm actually satisfy the promise?
   • If not, go back to Step 1 and iterate on the design.

Step 1: PRINT-IN-ORDER Specification

Let's say that PRINT-IN-ORDER takes a tree, represented by its root node treenode and promises to print the keys of the tree in sorted order.

Step 2: Base Case

Arguably, the simplest possible tree to print is the empty tree! To print an empty tree, just do nothing.

You could also have said a tree with only one item; in that case we just need to print the key. That's also a reasonable base case!

For now we'll stick with using an empty tree as our base case, because it simplifies the algorithm a bit.

Step 3: Recursive Step

In this step we assume that PRINT-IN-ORDER would work if we called it on a smaller subtree, and then we figure out how to use that to print the whole tree.

We know that all the keys in the left subtree are smaller than the key in the root, which is smaller than all the keys in the right subtree.

So to print the keys from smallest to largest, we need to print the left subtree, then the key in the root, and then the right subtree.

Step 4: Final Pseudocode

PRINT-IN-ORDER(treenode)
    if there is a treenode (i.e., this subtree is not empty)
        PRINT-IN-ORDER(treenode.leftSubtree)   // Print the left subtree in order
        PRINT(treenode.key)                               // Print the key in the root
        Print-In-Order(treenode.rightSubtree)    // Print the right subtree in order
     // else, do nothing (base case)

Here's a video walking through an in-order traversal:

(When logged in, completion status appears here.)

Previous Page Next Page