Recursively finding words in a hashmap using tries

Question

My method should add the associated key/value pair to the trie and if the key is already in the trie, the value should be updated. However I am not quite sure what Im doing wrong, its my first time using tries. So I am currently working on my put method and I have the following:

public void put(TrieMapNode current, String curKey, String value){
if(current.getChildren().containsKey(curKey))
      value = current.get(key);
      curKey =value;

  put(current.getChildren().get(curKey), curKey, value);

}

Any help would be greatly appreciated thanks!

Answer 1

In your current implementation, you will not benefit from the advantages of a trie. That is because at the root node, you have one child for each string you encounter.
That is not the way a trie is built. Each node of your trie can have at most one child per character (the elements that form strings).
So your method should look more like the following:

public void put(TrieMapNode current, String key, String value, int depth){
if (depth == key.length()){
   current.value = value;
} else {
    char curChar = key.charAt(depth);
    if(!current.getChildren().containsKey(curChar)){
        TrieMapNode newNode = new TrieMapNode();
        current.getChildren().put(curChar, newNode);
    }
    put(current.getChildren().get(curChar), curKey, value, depth + 1);
}

The main mistake you did was to consider the key as a whole when inserting/updating in your trie. This would have resulted in a root node having one child node for each key in your map (so a ton of children), but with a very limited depth (the root node, its children and that's it).

In the implementation I proposed you, a node has one child per possible character (a bounded number, 26, 52, anyway a small and bounded number).
And its depth is not limited to one, because as you can see in the else block, we create a node if the one we look for did not exist (when you start you only have a root node, so you need to plan for the case where new node are created), and we also call recursively put on a child of the current node. So the value will be stored at a depth equal toi the length of its key.