If we have a correctly made binary search tree, how could we EASILY find the first key field in the tree?
Start at the root, go left all the way down.
How would we find the last key field in the tree?
Start at the root, go right all the way down.
How do we find the "next" and "prev" entries to a node?
If the node exists?
If the node doesn't exist?
While we search, keep track of next-so-far and
prev-so-far. They both start at empty string.
If we move right update psf to match the node we just exited.
If we move left updata nsf to match the node we just exited.
If we find the node we're looking for:
If the node has a right child, then next is right once, left all the way down.
Otherwise, next is our nsf.
If the node has a left child, then prev is left once, right all the way down.
Otherwise, prev is our psf.