How do I print all the words out in a Trie?

Question

I have a Ternary Search Tree (Trie) and I want to print out all of the words in it.

How do I go about this using this current implementation that I have below? I have a standard put method to add new words to the tree. I was attempting to print the words using an in-order traversal, but I'm unsure how exactly to complete the function.

class TST {
    private Node root;

    public void put(String key, int value) {
        root = put(root, key, value, 0);
    }

    private Node put(Node node, String key, int value, int index) {
        char c = key.charAt(index);

        if( node == null ){
            node = new Node(c);
        }

        if( c < node.character ){
            node.left = put(node.left, key, value, index);
        }else if( c > node.character ){
            node.right = put(node.right, key, value, index);
        }else if( index < key.length()-1 ){
            node.middle = put(node.middle, key, value, index+1);
        }else{
            node.value = value;
        }

        return node;
    }

    public Integer get(String key) {
        Node node = get(root, key, 0);

        if (node == null) {
            return null;
        }

        return node.value;
    }

    public Node get(Node node, String key, int index) {
        if(node == null) {
            return null;
        }

        char c = key.charAt(index);

        if (c < node.character) {
            return get(node.left, key, index);
        } else if (c > node.character) {
            return get(node.right, key, index);
        } else if(index < key.length() -1) {
            return get(node.middle, key, index);
        } else {
            return node;
        }
    }

    public void inorderTraversal(Node node) {
        System.out.print(node.character + ":" + node.value + " ");

        if(node.left != null) {
            inorderTraversal(node.left);
        }
        if(node.middle != null) {
            inorderTraversal(node.middle);
        }

        if(node.right != null) {
            inorderTraversal(node.right);
        }
    }

    public void traverse() {
        inorderTraversal(root);
    }
}

public class Main {
    public static void main(String[] args) {
        TST tst = new TST();
        tst.put("This",3);
        tst.put("There",4);
        tst.put("Them",5);
        tst.put("High",6);
        System.out.println(tst.get("T"));
        tst.traverse();
    }
}

class Node {
    public char character;
    public Node left, right, middle;
    public int value;

    public Node(char character) {
        this.character = character;
    }
}

Welcome on SO, I hope you've took the small [tour] of SO already. What is the problem exactly ? See [ask] — AxelH, Dec 27 '17 at 13:18
Thanks :), I just want to be able to print out all the words that are stored in the tree I can print out the Nodes fine but not the words. Its supposed to be a fairly common interview question but I can't find out how to do so. — , Dec 27 '17 at 13:24
Okay so I added the Node and Main class here I enter in words to the tree each of the characters of these words are given a node and a value, I can print out all the characters fine but what I want is to print out the words that are in the tree. Heres a visualization for treis https://www.cs.usfca.edu/~galles/visualization/TST.html — , Dec 27 '17 at 13:38
Ok, I read that one wrong... you need to concat your character in a collection until you reach the end. So that you can rebuild the value. If you want every values, you will need to remove a character each time you "go up" to add the next ones. PS: with a [mcve], I would probably have read your question with more attention ;) — AxelH, Dec 27 '17 at 13:57
I'll try in the future, first time asking a question here lol will bear that in mind for the future, do you have any idea how to implement it, I'm thinking of something like a DFS but am unsure? — , Dec 27 '17 at 14:01

Bernhard Barker · Accepted Answer · 2017-12-27T15:30:07.017

Since each node only stores a single character, you need to pass along a String (or StringBuilder, if you're trying to be efficient) representing the prefix defined by the path from the root when doing your traversal.

As per the definition of a ternary search tree, you should only append to this prefix when going to the middle node.

An example implementation:

public void inorderTraversal(Node node, String word) {
    // handle end of word
    if (node.value != 0) {
        System.out.println(word + node.character + ": " + node.value);
    }

    if(node.left != null) {
        inorderTraversal(node.left, word);
    }

    if (node.middle != null) {
        inorderTraversal(node.middle, word + node.character);
    }

    if(node.right != null) {
        inorderTraversal(node.right, word);
    }
}

public void traverse() {
    inorderTraversal(root, "");
}

Demo.

It's also possible to store the String representing the full word at each node during construction, since you already have the complete word in your put method (if you're not worried about the memory usage).

Note that this / your code doesn't allow for mapping words to a 0 value - one way to deal with that is to use Integer instead of int, then you can use != null to check for the end of a word.

Thanks a million, this was really annoying me :), could use values for that because the last letter of each word holds a value where other nodes that are in the middle of a sentence have the value of 0 or null in generic cases. — , Dec 27 '17 at 15:33

How do I print all the words out in a Trie?

1 Answers1