Adding an nth Method

In this optional part of Homework 7, you'll add a method to your TreeSet<T> class template that allows users to retrieve the nth smallest element in the tree (using zero-based indexing). For example, if the tree contains the elements { "apple", "banana", "cherry", "date" }, then calling nth(0) would return "apple", nth(1) would return "banana", and so on.

One of the benefits of storing the size of each subtree in the nodes of the tree is that it allows us to efficiently navigate to the nth element without having to traverse the entire tree. Look at the following diagram:

In this diagram, you can see the nodes of the tree, their sizes (in blue), and the indices of the elements (in green). There are two things to notice here:

• The indices of the elements (which correspond to their order in sorted order) themselves form a binary search tree.
• We don't actually need to store the indices explicitly, because we can compute them from the sizes of the subtrees. Specifically,
  • The index of the root node (within its subtree) is equal to the size of its left subtree.

The algorithm for nth is as follows:

NTH(subtree, n):
    if the subtree is empty,
        throw an exception (n is out of bounds)
    otherwise:
        left_size = size of left subtree
        if n == left_size,
            return the value at this node
        else if n < left_size,
            return NTH(left subtree, n)
        else,
            return NTH(right subtree, n - left_size - 1)

Coding It Up (Basic Version)

The most obvious version of nth is to provide a public member function with the signature

template <typename T>
const T& TreeSet<T>::nth(int n) const;

and translate the provided pseudocode into a private helper function that takes a Node* parameter for the subtree to search.

It's quite straightforward to both implement this function and test it. You can add test cases that build trees with known contents and then check that nth returns the expected values for various indices.

But it's also easy to go a bit further…

Coding It Up (Enhanced Version)

An alternative design is to provide an iterator-based version of nth, with the signature

template <typename T>
TreeSet<T>::const_iterator TreeSet<T>::nth(int n) const;

You can look back at the lower_bound implementation in the previous section for inspiration on how to build an iterator to return. The logic for navigating the tree is the same as in the first version, but instead of returning the value at the node, you will push the node onto the iterator's stack when you find it, and then return the iterator.

One key difference is that when you reach a null pointer (i.e., you've gone past a leaf), you will return the iterator you've built up so far, rather than throwing an exception. If the user called nth with an out-of-bounds index, the iterator will simply be equal to end().

Our sample solution implements this enhanced version of nth. If you include tests for nth in your treeset-test.cpp, you can leave them in place when you submit your homework if you like—however, you must comment out the tests for the simpler version because our sample solution returns an iterator, not a value, so your tests won't compile.

Say What You Did…

Don't forget to include a description of what you did in your Fun.md file!

(When logged in, completion status appears here.)