I'm trying to create an insert method for a trie in Java, where the method takes a string as an input, and checks to see if a node for each letter exists in the trie: I've attempted this once with a simple Array, and once with a HashMap as seen here:
Array Approach
// Simple Array approach
public class trieNode {
char value = '\n';
final static int ALPHA_SIZE = 26;
int count = 0;
trieNode[] children = new trieNode[ALPHA_SIZE];
boolean isEnd = false; //signifies the end of a word
static trieNode root;
trieNode parent;
//constructor for the class
trieNode(){
for(int i = 0; i < ALPHA_SIZE; i++) {
children[i] = null;
}
}
//add a node to the trie.
static void trieInsert(String word) {
trieNode search = root;
for( int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a'; //There doesn't seem to be any problem here, for example when the given char is c, index returns 2.
if(word.charAt(i) == search.children[index].value) { //WHERE THE ERROR OCCURS
search.children[index].count++;
search.children[index].isEnd = false;
search.children[index] = new trieNode();
}
}
System.out.println(word + " has been added successfully to the trie.");
}
HashMap Approach:
public class TrieNode {
final static int ALPHABET_SIZE = 26;
char value;
boolean isEndOfWord;
boolean isTrieLeaf;
HashMap<Character, TrieNode> children = new HashMap();
int count = 0;
TrieNode root;
TrieNode parent;
TrieNode(){
}
void trieInsert(String word) {
TrieNode search = root;
for(int i = 0; i < word.length(); i++) {
if(search.children.containsKey(word.charAt(i))) { //WHERE THE ERROR OCCURS
search.children.get(word.charAt(i)).count++; //increase the count by one.
search = search.children.get(word.charAt(i)); //this character must already be in the trie, check the rest of the word
}
else {
search.children.put(word.charAt(i), new TrieNode()); //create a new node in the map for the character.
search = search.children.get(word.charAt(i)); //move to the newly created node and start the process again.
search.children.get(word.charAt(i)).count++; //update the base variables for the Trie.
search.children.get(word.charAt(i)).isEndOfWord = false;
}
if((word.length()-i) == 1)
search.children.get(word.charAt(i)).isTrieLeaf = true; //if it's the last word in the trie, change that value to true.
}
}
}
The problem occurs when I test them (ex trieInsert("cat")), I always get a null pointer exception at each if statement, but I was under the assumption that you could use null as a comparison in this manner, and you could set objects equal to null in this case?
Example Test
public class main {
public static void main(String[] args) {
TrieNode Trie = new TrieNode();
Trie.trieInsert("cat");
}
}
Am I missing something, and if so what can I do to fix it.
