Collecting all words in a Trie in Java

Question

I am trying to implement a method that will add all the words in the Trie to a List. I am using a Hashmap to store the character and reference node of the child node. Characters should include only letters a-z. This is my implementation of the node:

class Node {
    char c;
    HashMap<Character, Node> children = new HashMap<>();
    boolean isCompleteWord;

    public Node(char c){
        this.c = c;
        isCompleteWord = false;
    }
    public Node(){}
}

I'm not quite sure where to start with it, the leaf node will be able to tell me whether the word is complete, so I could traverse down the Trie till the leaf node is reached and append the characters to a string maybe, but once that word has been added how can I traverse through different branches of the trie to add other words?

One Q. you are allowed to store only az chars, nothing else even though your Trie might hold other chars? — MS90
The Trie will only be storing chars from a-z, validation is implemented in the insert method to ensure this — Sean2148

m.raynal m.raynal · Accepted Answer · 2019-03-19T16:03:32

First things first. You actually do not need to store a character attribute in your node class, since it is already implicitely stored in the children attribute of its parent node.
So your Node class can actually be:

class Node {
    HashMap<Character, Node> children = new HashMap<>();
    boolean isCompleteWord;

    public Node(){
        isCompleteWord = false;
    }
}

Also, like all rooted trees, your Trie will require a root. You will need a root before storing any word in your Trie.

root = new Node();

The root node represents the empty string, so if you need to store it, you will have to check the isCompleteWord attribute of root.

Then, to insert a word, say myWord, you need to start from your root, and apply the following rule:
- Consider the first letter myWord[0], say 'c'. You need to distinguish 2 cases, whether root contains the key 'c', or not. If it does not contain the word, you will need to create a new node in your Trie. Otherwise, you just need to continue to 'walk' along branches.
- Once you arrive on the last letter, you will only need to set the attribute isCompleteWord to true. Here is a possible (totally untested) implementation of addWord, which adds a word in the Trie, and returns true if it was there already, false otherwise.

public bool addWord(Node node, String word, int idx){        
    if (idx == word.length() -1){ 
    // we're checking the last letter
        bool result = node.isCompleteWord;
        node.isCompleteWord = true;
        return result;
    } else {
        if (!node.children.containsKey(word.charAt(idx)){ 
        // no child with this letter, create one
            child = new Node()
            node.children.put(word.charAt(idx), child);
        } 
        return addWord(node.children(word.charAt(idx)), word, idx+1);
    }
}

To add a word, say myWord, in a Trie, you only have to call it as follows:

addWord(root, myWord, 0);

A function that checks if a word is stored in the trie is very similar to the one which adds words.

public bool containsWord(Node node, String word, int idx){        
    if (idx == word.length() -1){ 
        return node.isCompleteWord;
    } else {
        if (!node.children.containsKey(word.charAt(idx)){ 
        // no child with this letter, the word is not in the trie
            return false;
        } else {
            return containsWord(node.children(word.charAt(idx)), word, idx+1);
        }
    }
}

Collecting all words in a Trie in Java

1 Answers