Adapting pseudocode to java implementation for finding the longest word in a trie
- by user1766888
Referring to this question I asked: How to find the longest word in a trie?
I'm having trouble implementing the pseudocode given in the answer.
findLongest(trie):
//first do a BFS and find the "last node"
queue <- []
queue.add(trie.root)
last <- nil
map <- empty map
while (not queue.empty()):
curr <- queue.pop()
for each son of curr:
queue.add(son)
map.put(son,curr) //marking curr as the parent of son
last <- curr
//in here, last indicate the leaf of the longest word
//Now, go up the trie and find the actual path/string
curr <- last
str = ""
while (curr != nil):
str = curr + str //we go from end to start
curr = map.get(curr)
return str
This is what I have for my method
public static String longestWord (DTN d) {
Queue<DTN> holding = new ArrayQueue<DTN>();
holding.add(d);
DTN last = null;
Map<DTN,DTN> test = new ArrayMap<DTN,DTN>();
DTN curr;
while (!holding.isEmpty()) {
curr = holding.remove();
for (Map.Entry<String, DTN> e : curr.children.entries()) {
holding.add(curr.children.get(e));
test.put(curr.children.get(e), curr);
}
last = curr;
}
curr = last;
String str = "";
while (curr != null) {
str = curr + str;
curr = test.get(curr);
}
return str;
}
I'm getting a NullPointerException at:
for (Map.Entry<String, DTN> e : curr.children.entries())
How can I find and fix the cause of the NullPointerException of the method so that it returns the longest word in a trie?
