Yahoo Interview Question
Software Engineer / DevelopersI went through Trie data structure where trie can be used to sort keys. Below are the steps from Wiki.
Sorting
Lexicographic sorting of a set of keys can be accomplished with a simple trie-based algorithm as follows:
1 Insert all keys in a trie.
2 Output all keys in the trie by means of pre-order traversal, which results in output that is in lexicographically increasing order. Pre-order traversal is a kind of breadth-first traversal. In-order traversal is another kind of depth-first traversal that is more appropriate for outputting the values that are in a binary search tree rather than a trie.
I could not understand the second step. (Use the example trie given on wiki page). How can one do pre-order traveresal with a tree that is not binary. In example if i simply visit every root (pre-order traversal) i would end up getting to, tea, ted which is not sorted. Since tea must come before to. Can some1 explain with an example how to sort using trie
use a TRIE.. http://en.wikipedia.org/wiki/Trie
- hgk October 25, 2009