Trie (Prefix Tree) Implementation in Java

A Trie, also known as a prefix tree, is a tree-like data structure that is used to store a dynamic set of strings, where the keys are usually strings. Tries are particularly useful for tasks like autocomplete, spell-checking, and IP routing.

Program Structure

The Trie implementation consists of two main classes:

• TrieNode: Represents a single node in the Trie.
• Trie: Manages the Trie structure, allowing insertion and search operations.

1. TrieNode Class

This class represents a node in the Trie. Each node contains:

• An array of TrieNode references for its children (one for each letter of the alphabet).
• A boolean flag isEndOfWord that marks whether the node represents the end of a word.

2. Trie Class

This class manages the Trie, providing methods to insert words and search for them. The main methods are:

• insert(String word): Inserts a word into the Trie.
• search(String word): Searches for a word in the Trie and returns true if it exists.
• startsWith(String prefix): Checks if there is any word in the Trie that starts with the given prefix.

Java Code Implementation

TrieNode Class


public class TrieNode {
private TrieNode[] children;
private boolean isEndOfWord;

public TrieNode() {
children = new TrieNode[26]; // Assuming only lowercase a-z letters
isEndOfWord = false;
}

public TrieNode getChild(char ch) {
return children[ch – ‘a’];
}

public void setChild(char ch, TrieNode node) {
children[ch – ‘a’] = node;
}

public boolean isEndOfWord() {
return isEndOfWord;
}

public void setEndOfWord(boolean endOfWord) {
isEndOfWord = endOfWord;
}
}

Trie Class


public class Trie {
private TrieNode root;

public Trie() {
root = new TrieNode();
}

public void insert(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
if (current.getChild(ch) == null) {
current.setChild(ch, new TrieNode());
}
current = current.getChild(ch);
}
current.setEndOfWord(true);
}

public boolean search(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
current = current.getChild(ch);
if (current == null) {
return false;
}
}
return current.isEndOfWord();
}

public boolean startsWith(String prefix) {
TrieNode current = root;
for (char ch : prefix.toCharArray()) {
current = current.getChild(ch);
if (current == null) {
return false;
}
}
return true;
}
}

Conclusion

This Trie implementation in Java provides a simple and efficient way to store and retrieve strings, making it an excellent choice for tasks like autocomplete and spell-checking. By understanding and implementing this data structure, developers can handle prefix-based queries with ease.