6
\$\begingroup\$

I created a Java Trie as part of a project someone challenged me to do. I'm not sure that this is the most efficient way to go about producing a Trie, I know that this works but I was hoping someone with some professional experience could enlighten me on anything I might be doing fundamentally wrong.

I'm studying computer science in college and have no professional experience with development.

I'm mainly curious to know what you think about this with respect to:

  1. My use of methods, some are static while others are not. For the scope of the methods, I feel like I might have been better off putting the entire search function or getWords function inside the Trie class and not the TrieNode class, but I was unable to figure out how to do that logically.

  2. The use of comments or the logical flow of the code. Would this be a nightmare in an office or is this about what you would hope for?

  3. Efficiency of the code. I know recursion can be demanding, but I think that the nature of the way this is created has made it more efficient than lets say a massive list of words. I would need a giant library.txt file to test that theory, though and I don't really have one to work with.

Trie class:

import java.util.List;


public class Trie {

    private TrieNode root;
    private List<String> wordList;

    public Trie(){
        root = new TrieNode();
    }

    public Trie(String word){
        this();
        this.addWord(word);
    }

    public void addWord(String word){
        root.addWord(word.toLowerCase());
    }

    public List<String> getWords(){
        wordList = root.getWords(root, "");
        return wordList;
    }

    public boolean containsWord(String word){
        return root.containsWord(root, word);
    }
}

TrieNode class:

import java.util.*;


class TrieNode {

    //Variables used in addWords

    private boolean isWord;
    private boolean hasChildren;
    private char character;
    private Map<Character, TrieNode> children = new HashMap<>();

    //Variables for search method
    private static List<String> wordList = new ArrayList();;


    public TrieNode(){
        hasChildren = false;
        isWord = false;
    }

    public TrieNode(String word){
        this();
        addWord(word);
    }

    /* Recursively add nodes to the tree. Each node contains a map with letters.
     * If the next letter in a word is not inside the map, it is added.
     * */
    public void addWord(String word){

        char firstChar = word.charAt(0);

        //If current node has no more letters, add subsequent letters
        if (children.get(firstChar) == null){
            this.hasChildren = true;
            // If word has more than 1 character left
            if(word.length() > 1){
                TrieNode tn = new TrieNode();
                children.put(firstChar, tn);
                children.get(firstChar).addWord(word.substring(1));
            }
            // If only 1 character remains in the word
            else{
                children.put(firstChar, new TrieNode());
                children.get(firstChar).isWord = true;
            }
            // Once the node was added, set the character value for future reference
            children.get(firstChar).character = firstChar;
        }

        // If first letter is already in the index, send subsequent characters into that node.
        else
            children.get(firstChar).addWord(word.substring(1));
        }

    // Static method starts with Root and blank values. 
    public static List<String> getWords(TrieNode node, String chars){

        chars += node.character;
        // Traverse trie adding characters to the string until a word is found
        if(node.isWord){
            wordList.add(chars.trim());
        }
        // If more letters still remain, continue traversing
        if(node.hasChildren){
            for(Character c: node.children.keySet()){
                getWords(node.children.get(c), chars);
            }
        }
        // If the end of a branch is reached, reset the string
        else{
            chars = "";
        }

        // Sort and return the list of words
        Collections.sort(wordList);
        return wordList;
    }


    static boolean hasWord = false;
    public static boolean containsWord(TrieNode node, String word){

        char letter = word.charAt(0);
        // If current node does not contain next letter, word isn't in list
        if(node.children.get(letter) == null)
            hasWord = false;
        // If the former if passed, and 1 character remains, check to see if last char node is a word
        else if(word.length() == 1){
            if(node.children.get(letter).isWord == true)
                hasWord = true;
            else
                hasWord = false;
        }
        // If more letters remain, recursively call this method with a substring
        else{
            containsWord(node.children.get(letter), word.substring(1));
        }
        return hasWord;
    }
}

And lastly the class that calls this:

public class TrieProject {


    public static Trie t;
    public static void main(String[] args) {

        t = new Trie();
        t.addWord("h");
        t.addWord("ha");
        t.addWord("hhha");
        t.addWord("samsung");
        t.addWord("sampson");
        t.addWord("Double Vision");

        for(String s: t.getWords()){
            System.out.println(s);
        }
        System.out.println(t.containsWord("samsun"));
    }
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ also small note, while you are lowercasing the words you are saving the contains function is not lowered, so it will always return false. especially surprising seeing as the word added will not match the same word when checked again! \$\endgroup\$ Feb 14 '14 at 9:35
7
\$\begingroup\$

In general, with data structures containing nodes, it is common practice for the node class to be a simple container, and not a computational power house. You have reversed this concept, and made the Node the engine.... which is unexpected... and is why you feel your class is 'awkward' with the static methods, etc. Rearranging where the logic is will make a big difference.

This is a big change, and going through your code as it is, while saying "everything is in the wrong place" is not productive.... it's better for me to show you what it will look like if the Node is a simple container, and the actual Trie does the heavy lifting.

Things about this re-factor that are significant, and you should look for are:

  • The TrieNode is an inner (nested) class, and it does not know anything about any other class (except it's own state).
  • I use iteration to add, and 'contains' words, not recursion. This only works because the logic is outside the TrieNode
  • I use recursion to getWords(), with a 'stack' that contains the characters.
  • I have added a size() method, and I also track the deepest point.
  • there is no static content at all, except for EMPTYNODES
  • I thought it would be 'cute' to return the words in alphabetical order.
  • it supports the empty-string.

So, the point of my answer is to say you chose the less-appropriate code structure. Nodes should be containers (and private, and light-weight). The Trie itself contains the state data, and is what does the heavy lifting. This is the opposite of what you have.

I have left the data structures similar to what you have. If I were doing this myself, I would probably be using a large data set, and I would find a way to get rid of the children Map, and replace it with a more space-saving primitive array structure of some sort.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class Trie {

    private static final TrieNode[] EMPTYNODES = new TrieNode[0];

    private static final class TrieNode implements Comparable<TrieNode> {

        private final char character;
        private boolean isWord = false;
        private Map<Character, TrieNode> children = null;

        public TrieNode(char ch) {
            character = ch;
        }

        public TrieNode getOrCreateChild(char ch) {
            if (children == null) {
                children = new HashMap<>();
            }
            TrieNode kid = children.get(ch);
            if (kid == null) {
                kid = new TrieNode(ch);
                children.put(ch, kid);
            }
            return kid;
        }

        public TrieNode get(char ch) {
            return children != null ? children.get(ch) : null;
        }

        public void setWord() {
            isWord = true;
        }

        public boolean isWord() {
            return isWord;
        }

        public char getChar() {
            return character;
        }

        public TrieNode[] getChildNodes() {
            if (children == null) {
                return EMPTYNODES;
            }
            TrieNode[] result = children.values().toArray(new TrieNode[children.size()]);
            Arrays.sort(result);
            return result;
        }

        @Override
        public int compareTo(TrieNode o) {
            // cheap way to sort alphabetically.
            return (int)character - o.character;
        }

    }



    private final TrieNode root;  // fix - make root final.
    private int size = 0; // how many words
    private int depth = 0; // longest word

    public Trie(){
        // root has null character.
        root = new TrieNode((char)0);
    }

    public void addWord(String word){
        TrieNode node = root;
        int wdepth = 0;
        for (char ch : word.toLowerCase().toCharArray()) {
            node = node.getOrCreateChild(ch);
            wdepth++;
        }
        if (!node.isWord()) { // fix - only add new words....
            node.setWord();
            size++;
            if (wdepth > depth) {
                depth = wdepth;
            }
        }
    }

    public boolean containsWord(String word){
        TrieNode node = root;
        for (char ch : word.toLowerCase().toCharArray()) {
            node = node.get(ch);
            if (node == null) {
                break;
            }
        }
        return node != null && node.isWord();
    }

    public int size() {
        return size;
    }

    public List<String> getWords() {
        // set up a recursion call.
        List<String> result = new ArrayList<>(size);
        char[] charstack = new char[depth];
        getWords(root, charstack, 0, result);
        return result;
    }

    private void getWords(final TrieNode node, final char[] charstack, final int stackdepth, final List<String> result) {
        if (node == null) {
            return;
        }
        if (node.isWord()) {
            result.add(new String(charstack, 0, stackdepth));
        }
        for (TrieNode kid : node.getChildNodes()) {
            charstack[stackdepth] = kid.getChar();
            getWords(kid, charstack, stackdepth + 1, result);
        }
    }

    public static void main(String[] args) {
        Trie t = new Trie();
        t.addWord("h");
        t.addWord("ha");
        t.addWord("hhha");
        t.addWord("samsung");
        t.addWord("sampson");
        t.addWord("Double Vision");

        List<String> words = t.getWords();

        for(String s : words){
            System.out.println(s);
        }
        System.out.println(t.containsWord("samsun"));
    }

}
\$\endgroup\$
3
  • \$\begingroup\$ Just re-reading my answer, there's one change, and one bug to consider.... I will edit the answer, but root could/should be final, and size should only increase if it is a new word... I have marked the code with // fix \$\endgroup\$
    – rolfl
    Feb 14 '14 at 17:21
  • 1
    \$\begingroup\$ I wanted to add that I just had an interview for a Java position, and they really didn't like recursive solutions to anything. They preferred the stack implementation because it is more efficient. So again, good answer. \$\endgroup\$
    – leigero
    Feb 20 '14 at 4:17
  • \$\begingroup\$ You're welcome, and I wish you success in your hunt! \$\endgroup\$
    – rolfl
    Feb 20 '14 at 4:30
3
\$\begingroup\$

Your Trie class looks fine.

In TrieNode I can see a few problems with you algorithm:

addWord

  1. You do not properly check for the edge conditions, i.e. when word is null or empty.
  2. You are setting private members of your child's instances in the parent - you should move that to your constructor.
  3. Your code is not DRY, since you call children.get(firstChar).addWord(word.substring(1)) twice.

I would have re-written the method to something like this:

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

public void addWord(String word){
   if (word == null) return;
   if (word.length() == 0) {
     isWord = true;
     return;
   }
   char firstChar = word.charAt(0);

   //If current node has no more letters, add subsequent letters
   if (children.get(firstChar) == null){
       this.hasChildren = true;
       children.put(firstChar, new TrieNode(firstChar));
   }

   children.get(firstChar).addWord(word.substring(1));
}

getWords

  1. You use a static member to keep your wordList. This is problematic for a couple of reasons:
    • You cannot have more than one Trie in your program...
    • Each time you call getWords you compound your new word structure on lists from previous calls, since you never clean it up...
  2. You use recursion, but treat your variables as in iteration - chars = ""; is redundant, for example.

I would have made the getWords method not static, and change the one in Trie as follows:

Trie class:

public List<String> getWords() {
  return Collections.sort(root.getWords(new List<String>(), ""));
}

TrieNode class:

public List<String> getWords(list, prefix) {
  if (node.isWord) {
    list.add(prefix);
  }

  prefix += this.character

 for(TrieNode child: children.values()) {
   child.getWords(list, prefix);
 }
 return wordList;
}

Changes is containsWord() will be similar, I'm leaving this as an exercise for the OP.

Another small observation - your root does not have a character, which might prove problematic...

\$\endgroup\$
6
  • \$\begingroup\$ I left the root blank because I found it more problematic to have a root node with a character. How can you add the word "sample" to a tree whose root character is a 't'? The way it is, each level of the tree can have all 26 letters of the alphabet if necessary. Great points, thank you for taking the time. In the improved getWords() method, you removed the node from the method signature. I'm assuming that should be if(this.isWord) instead? \$\endgroup\$
    – leigero
    Feb 14 '14 at 10:33
  • \$\begingroup\$ A blank root node is fine. No problem, and it allows you to store the 'empty string' "" as well. \$\endgroup\$
    – rolfl
    Feb 14 '14 at 12:15
  • \$\begingroup\$ @rolfl, since character is a char - its default value is not a null (it is a primitive) or an empty string - it is a '\u0000' which is not a printable character - all words will begin with a small rectangle... \$\endgroup\$
    – Uri Agassi
    Feb 14 '14 at 16:37
  • \$\begingroup\$ @leigero - I agree that the root node should not have a character, but it would need some special attention in the code. Maybe have an isRoot attribute to the class... Anyway, if you like my answer you can mark it as the correct answer :-) \$\endgroup\$
    – Uri Agassi
    Feb 14 '14 at 16:39
  • 1
    \$\begingroup\$ The nature of code review should warrant more than one correct answer. You've both been very helpful, although the answer @rolfl provided was almost exactly what I was looking for, so I went with his. You both deserved a +1 though. \$\endgroup\$
    – leigero
    Feb 14 '14 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.