Trie string iterations

Question

 0円
 / \
 a b-a-t-s
 /|\
m s t

which contains [am, as, at, bat, bats]

The goal I'm trying to reach is to iterate through the trie to find if there's a next word or not, then if so get that word.

I would like to know your opinion on my approach.

The goal for this is that, at any point in the trie if there is a node that hasn't been visited, there's another word.

public boolean hasNext() {
 if (position < this.trie.nodeCount()) return true;
 return false;
}

What I'm trying to go for here is to check to see if the trie is not empty, then at the first trienode in the trie traverse it's children and descendants to find the next word in the trie. so for the trie above it would would go to a then first to m then back to a to s, then t. then eventually go onto b and it's children. then on the way, if it passes a full word, it will repeat that. so in this case, since bat is part of bats it would return 'bat' first then on the next iteration return bats

The logic in plain words is

string temp = null
 if has next
 while current != null
 look at current nodes children
 keep track of nodes visited 
 (temp += char at that node)
 current = current nodes next node in trie (so a step down the trie)
 if fullword at that node found return next
 return false;

I also thought of trying a pre-order traversal but couldn't figure out how to do it with the arrays.

Current implementation:

public String next() {
 String next = null;
 if(hasNext()){
 current = trie.root.children[position];
 while(!current.children[position].isEndOfWord()){
 position++;
 current = current.children[position];
 next += current.letter;
 if (current.isEndOfWord()) return next;
 }
 }
 return null;
}

Here's the declaration of the trienodes:

 protected char letter = ' ';
 protected TrieNode parentNode = null;
 protected boolean fullWord = false;
 protected TrieNode[] children = new TrieNode[26];
 protected int prefixes = 0;
 public TrieNode(char letter, TrieNode parentNode){
 this.letter = letter;
 this.parentNode = parentNode;
 }

How the trie is built:

public void addWord(String s) {
 if (hasWord(s)) return;
 int index = 0;
 TrieNode current = root;
 char[] letters = s.toCharArray();
 while(index < s.length()){
 TrieNode child = current.children[letters[index] - 97];
 if(child == null){
 child = new TrieNode(letters[index], current);
 child.prefixes++;
 numOfNodes++;
 }
 current = child;
 index++;
 if(index == s.length()){
 current.fullWord = true;
 numOfWords++;
 }
 }
 }

Answer 1

This doesn't look too bad to me, though it would be nice to have the full source code that I could run. I'll comment on the things that stand out to me, though.

Unncessary logic

public boolean hasNext() {
 if (position < this.trie.nodeCount()) return true;
 return false;
}

can be written simply as

public boolean hasNext() {
 return position < this.trie.nodeCount();
}

Whitespace is your friend

This is purely stylistic, but to me

 if (hasNext()) {

is much easier on the eyes than

 if(hasNext()){

A lot of IDEs provide automatic formatting to do this for you, too (In Eclipse, Window -> Preferences -> Java -> Code Style -> Formatter).

More on the next method

• Avoid nulls if you can. See Google Guava's rational and Effective Java Item 43. If you initialize next to "" instead of null, you can avoid some potential errors downstream.

• This can be simplified:

  position++;
  current = current.children[position];
  

  to just

  current = current.children[++position];
  

• Alarm bells should be going off anytime you're iteratively adding to a String. You should be using a StringBuilder instead. Read more about them here.

• Using an if statement without brackets is rarely a good idea.

• Some standards discourage more than one return statement per method.

With that said, here is how I would refactor the method:

public String next() {
 StringBuilder next = new StringBuilder();
 if (hasNext()) {
 current = trie.root.children[position];
 while (!current.children[position].isEndOfWord()) {
 next.append(current.children[++position]);
 if (current.isEndOfWord()) {
 break;
 }
 }
 }
 return next.toString();
}

Regarding TrieNode

• Why are the fields protected? This suggests that the class is to be extended. If that's the case, TrieNode should be abstract (See Open-Closed principle and Effective Java Item 17: "Design and document for inheritance or else prohibit it").

• If letter and parentNode variables don't change, you can make them final (again, IDEs like Eclipse can also do this automatically for you).

• On the line

  protected TrieNode[] children = new TrieNode[26];
  

  26 is a magic number, and should be replaced with a constant.

Final thoughts on addWord

• Use a for loop instead of the current while loop. Then you can remove two lines that deal with updating index.

• Instead of

  TrieNode child = current.children[letters[index] - 97];
  

  you should be able to go

  TrieNode child = current.children[letters[index] - 'a'];
  

  which has the benefit of not using a magic number and is more clear.

• syb0rg: What a great first review! Keep up the good work!