'How to write a recursive function to find number of nodes in a Trie?
I am trying to create a size() function to return the number of nodes in my Trie but I am not sure what I need to change in TrieNode to make this possible. I create a Trie from a file with words in it and I would like it to return the number of nodes. So for a file with: cat car dog pick pickle I would like it to print trie size: 14 nodes.
class TrieNode {
public final Map<Character, TrieNode> children = new HashMap<>();
private boolean endOfWord;
static final int ALPHABET_SIZE = 26;
public Map<Character, TrieNode> getChildren() {
return children;
}
boolean isEndOfWord() {
return endOfWord;
}
void setEndOfWord(boolean endOfWord) {
this.endOfWord = endOfWord;
}
int size(TrieNode node) {
if(node == null)
return 0;
int total = 1;
for(TrieNode child : node.children)
total += size(child);
return total;
}
public static void main(String[] args) throws IOException {
Trie myTrie = new Trie();
try {
BufferedReader reader = new BufferedReader(new FileReader("test.txt"));
String line;
while ((line = reader.readLine()) != null)
myTrie.insert(line);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("Trie Size: " + myTrie.size() + " nodes");
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
