Java Program to Implement Trie Data Structure

A Java program to implement a trie uses a TrieNode class with an array of children and a boolean flag, and a Trie class with insert and search methods to add and find words in the trie.

Examples

InputInsert: "cat", Search: "cat"

Outputtrue

InputInsert: "dog", Search: "do"

Outputfalse

InputInsert: "apple", Search: "apple"

Outputtrue

How to Think About It

To implement a trie, think of it as a tree where each node holds links to child nodes for each letter. When inserting a word, move through nodes for each letter, creating new nodes if needed. To search, follow the nodes for each letter and check if the word ends at a node marked as complete.

Algorithm

1

Create a root node with empty children and end-of-word flag false.

2

For insert, start at root and for each character in the word, move to the child node or create it if missing.

3

Mark the last node's end-of-word flag true after inserting all characters.

4

For search, start at root and follow child nodes for each character.

5

If any character node is missing, return false.

6

Return true only if the last node's end-of-word flag is true.

Code

java

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

public class Trie {
    private TrieNode root;

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

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

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        System.out.println(trie.search("cat"));  // true
        System.out.println(trie.search("ca"));   // false
        trie.insert("car");
        System.out.println(trie.search("car"));  // true
    }
}

Output

true
false
true

Dry Run

Let's trace inserting "cat" and searching "cat" through the trie.

1

Insert 'c'

Root node has no child at index for 'c' (2), create new node.

2

Insert 'a'

Move to 'c' node, no child at index for 'a' (0), create new node.

3

Insert 't'

Move to 'a' node, no child at index for 't' (19), create new node and mark isEndOfWord true.

4

Search 'c'

Root has child at index 2, move to 'c' node.

5

Search 'a'

Move to 'c' node's child at index 0, move to 'a' node.

6

Search 't'

Move to 'a' node's child at index 19, move to 't' node, check isEndOfWord true, return true.

Operation	Character	Node Created	isEndOfWord
Insert	c	Yes	false
Insert	a	Yes	false
Insert	t	Yes	true
Search	c	No	false
Search	a	No	false
Search	t	No	true

Why This Works

Step 1: TrieNode Structure

Each TrieNode holds an array for 26 letters and a boolean to mark if a word ends here.

Step 2: Insert Method

Insert moves through nodes for each letter, creating new nodes if missing, and marks the last node as end of word.

Step 3: Search Method

Search moves through nodes for each letter and returns true only if the last node is marked as end of word.

Alternative Approaches

Using HashMap for children

java

import java.util.HashMap;

class TrieNode {
    HashMap<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

public class Trie {
    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) return false;
            node = node.children.get(c);
        }
        return node.isEndOfWord;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        System.out.println(trie.search("cat"));
        System.out.println(trie.search("ca"));
    }
}

Using HashMap allows dynamic character sets beyond 'a'-'z' but uses more memory and is slower than array indexing.

Complexity: O(m) time, O(m * n) space

Time Complexity

Insertion and search take O(m) time where m is the length of the word, because each character is processed once.

Space Complexity

Space is O(m * n) in worst case, where n is number of words and m is average length, due to new nodes created for unique prefixes.

Which Approach is Fastest?

Array-based children are faster for fixed alphabets, while HashMap-based is flexible but slower and uses more memory.

Approach	Time	Space	Best For
Array children	O(m)	O(m*n)	Fixed small alphabets, fast access
HashMap children	O(m)	O(m*n)	Dynamic alphabets, more memory