Trie (Prefix Tree) Data Structure in Java

A Trie, also known as a Prefix Tree, is a specialized tree-based data structure used to store a dynamic set of strings. It is particularly efficient for prefix-based searches.

Key Properties

• Each node represents a character of a string.
• The path from the root to a node represents a prefix.
• Efficient for auto-complete systems, spell checkers, and IP routing.

Java Implementation

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;
}

public class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = getNode(word);
        return node != null && node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        return getNode(prefix) != null;
    }

    private TrieNode getNode(String str) {
        TrieNode current = root;
        for (char ch : str.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) return null;
            current = current.children[index];
        }
        return current;
    }
}

When to use a Trie?

1. Autocomplete/Dictionary: Fast prefix lookups.
2. IP Routing: Longest prefix matching.
3. Data Compression: Efficiently storing common prefixes.