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: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.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?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));    }}
Trie (tree form) in Java
java;trie
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 TrieNodeI 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 EMPTYNODESI 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));    }}