Trie (tree form) in Java

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 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 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 children = new HashMap<>();

//Variables for

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 {

private final char character;
private boolean isWord = false;
private Map 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 getWords() {
// set up a recursion call.
List 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 result) {
if (node == null) {
return;
}
if (node.isWord()) {
result.add(new String(charstack, 0, stackdepth));
}
for (TrieNode kid

StackExchange Code Review Q#41630, answer score: 7