Prefix trees for auto suggest

Question

I wrote a quick prefix tree implementation. I know it may be far from perfect, but I need to make sure that I got the basics right.

My main concerns are:

1. Have I settled for the correct data structures?
2. Is this a scalable solution? What sort of problems can I run into if this is a huge tree?

public class PrefixTree {
//isLeaf would point out the end of a word in the tree
boolean isLeaf;
HashMap<Character, PrefixTree> map;

public PrefixTree() {
    map=new HashMap<Character, PrefixTree>();
    isLeaf=false;
}

//insert a new word into the tree
public void put(String s) {
    if(s.length()==0) {
        //if the word ends here, we need to point it out using the isLeaf
        //boolean field, and the insertion job is done, so return
        isLeaf=true;
        return;
    }
    //if the first character of the string doesn't exits
    //we create a new node for the and insert it into the map
    if(!map.containsKey(s.charAt(0))) {
        map.put(s.charAt(0), new PrefixTree());
    }
    //now this newly create node or if it already existed
    //would contain the rest of the substring
    map.get(s.charAt(0)).put(s.substring(1));
}

//tree travelsal to examine the contents of the tree
public void travelTree(String perm) {
    if(isLeaf) {
        System.out.println(perm);
    }
    if(map.size()==0) return;
    for(Character c:map.keySet()) {
        map.get(c).travelTree(perm+c);
    }
}

//this overloaded function is used as a helper function with the getSuggestions
//functions
//doesn't need to be called on from the root
public void travelTree(String perm, List<String> sl) {
    if(isLeaf) {
        sl.add(perm);
    }
    if(map.size()==0) return;
    for(Character c:map.keySet()) {
        map.get(c).travelTree(perm+c, sl);
    }
}    

public List<String> getSuggestions(String q) {
    //I am passing along this List object into the nested recursive calls 
    //from here onwards, is this a better approach than having every 
    //recursive function call create an arraylist object and append the 
    //return items and finally return the final list
    List<String> suggestions=new ArrayList<String>();
    getSuggestions(q, "", suggestions);
    return suggestions;
}

public void getSuggestions(String q, String perm, List<String> sl) {
    if(q.length()==0) {            
        travelTree(perm, sl);
        //we don't return as we need to go into further depth for more
        //suggestions
    }
    if(map.size()==0) return;
    if(q.length()>0 && map.containsKey(q.charAt(0))) {
        //make sure we call getSuggestions on specific node instead of
        //current instance's getSuggestions
        map.get(q.charAt(0)).getSuggestions(q.substring(1), perm+q.charAt(0), sl);
    }
}
}

Answer 1

Overall it looks like you have created a clean and simple piece of code there. I still have some suggestions for you:

Nitpicks:

• Your indentation could use some rethinking. By convention everything in curly braces is indented by one level (4 spaces / 1 tab). Your class body isn't indented "properly"

• Your Prefix tree could use some eager initialization. Your constructor is completely superfluous if you just declare your fields (which should be private, btw.) like the following:

  public class PrefixTree {
      // isLeaf [...]
      private boolean isLeaf = false;
      private Map<Character, PrefixTree> map = new HashMap<>();
  

  I have additionally changed the type of map to a Map (which is an interface) instead of HashMap. The advantage of that is: you can change the map implementation at any time you like.

Comments:

Your comments are overall clear and simple. They explain the why and the what though, which is not desirable for comments IMO. Comments in code should be explaining why some decisions were made. The code should be clean enough that the why is obvious.

Also there is a huge load of spelling mistakes in the comments. These mean additional mental strain, because the reader has to decode the actual word from the sentence context.

Additionally I see that many of your methods are commented wrt what they do. You should definitely use javadoc for that. It allows you to document methods (and their purpose) in a way readable to both the programmer and easily usable by IDEs:

/**
 * Insert a new word into the tree
 * 
 * @param s The word to be inserted
 */
public void put(String s) {

Scoping:

As mentioned in a sidenot earlier on in the nitpicks: Your fields should be private. I'd even go so far to say that map should also be final.

Additionally you are exposing a helper function (travelTree) to the public. IMO that method should definitely be private.

Your concerns:

1. Have you settled for the correct data structures?
   To me this one looks like a yes. Good job on chosing a map to represent the character choices at each tree node.

   But there is one big problem I have with the Type you're assuming to be used with the tree, namely String. While a String is rather "universal" I'd rather see you using CharSequence which is a superclass of String. It also exposes .length() and .charAt() methods. Only your call to .substring() would have to be changed to .subsequence(1, len - 1)

2. Is this a scalable solution? What kind of problems can I run into if this is a huge tree?
   Well it's rather simple. This solution is quite scalable, mostly since you're really effective with the memory you're using and since traversing the tree is mostly following pointers in a HashMap. What you have to expect though for large trees is extremely large memory consumption (unsurprisingly) and increased traversal times.

   You currently have no way of shortcutting a traversal through a solitary branch with a "long" word like "Xylophone". This means you might be "wasting" some time in traversal.

Summa Summarum:

The code is clean and relatively simple. There is minor violations of java conventions all over the place, comments have too many spelling errors, but your choice of data structure is a good one.

Overall: Well done, but you can do better ;)