Best way to print a balanced BST in random order?

Question

I'm sorry if this seems like a random question, but I have a database of over 100,000 name/value pairs (call them high scores, if you will) stored in a balanced binary search tree, AVL-style. Most of time, to list the scores, I print the BST with an in-order traversal or reverse-order traversal, but today I came across a need for printing the tree in random (or pseudorandom) order. Is there some accepted or optimal way of doing this: visit every node exactly once, but in an unpredictable fashion?

PS -- I thought about a breadth-first traversal, but since that always happens in the same way, it's not really random. There has to be some clever way, or some ideal interview answer, since this seems like a common problem; I just haven't come up with anything really clever outside of just marking nodes as visited, or creating an external tracking data structure.

Answer 1

I don't know why the answer to this isn't just taking the BST, linearizing it, and then print it out. I suppose that your concern here is that linearizing a data structure such as this may take a lot of memory. If this is the case, you can always pick out pieces of the tree, linearize them, and then jump around. Traversing pointers randomly and hoping for an ordering that will work well is a bad idea: you're always going to get screwed looking for the last node. If you have a complete binary tree, you can always come up with numbers and start from the root (essentially, you get the linearization for free from the completeness property of the tree).

EDIT:

I was less informed than I perhaps should be, because I recently discovered this article, though it's based on a functional implementation, it may be of use to you. I haven't read it all, so I don't know how it works for iterating through everything, but if you simply want to get a single node out, then you can use this..

http://okmij.org/ftp/Algorithms.html#random-tree-node