algorithm - How to list in an alphabetical order the words of a ternary search tree?

Question

How can I go about listing the words a TST contains in an alphabetical order?

Unlike BSTs where an in-order traversal will do the trick, this won't work TST. Neither would pre-order nor post-order traversals.

More so, the nodes of TST contain alphabets not words as opposed to the nodes of some BST implementation. And there are some alphabets which not be included when moving from the left nodes to right nodes.

I can seem to get my head around it.

The figure below show the list of words of a TST in alphabetical order.

Image from: http://www.geeksforgeeks.org/ternary-search-tree/

Answer 1

You can think of a ternary search tree as a hierarchy of different binary search trees - the black lines connect together nodes in the same BST, and the dotted lines link different BSTs together.

You can list off all the words in a TST by doing a modified inorder traversal. Specifically, do an inorder traversal, and at each node, recursively list off all of the words in the TST linked to the current node, prefixed by whatever letters are on the path so far.

Here's some pseudocode:

function tst_inorder_traversal(node) {
    _tst_inorder_traversal_aux(node, "");
}


function _tst_inorder_traversal_aux(node, prefix) {
    if (node is not null) {

        /* Start normal in-order traversal. 
          This prints all words that come alphabetically before the words rooted here.*/
        _tst_inorder_traversal_aux(node->left, prefix);

        /* List all words starting with the current character. */
        if (node marks the end of the word) 
            print(prefix + tree->character);

        _tst_inorder_traversal_aux(node->middle, prefix + node->character);

        /* Finish the in-order traversal by listing all words that come after this word.*/
        _tst_inorder_traversal_aux(node->right, prefix);
    }
}

Hope this helps!