Trie Data Structure in Java 🖥️

This project implements a Trie, also known as a Prefix Tree, in Java.

A Trie is a tree-like data structure used to store strings efficiently. It is especially useful when we need fast searching based on prefixes, such as dictionary lookup, autocomplete, spell checking, and word storage.

Project Files

Trie.java
TrieUse.java

Important Note About TrieNode

In this project, the TrieNode class is implemented together with the Trie implementation inside Trie.java.

It is not kept as a separate public class because TrieNode is only used internally by the Trie data structure. This keeps the project simple and beginner-friendly.

What is a Trie?

A Trie stores words character by character.

Each node represents one character, and paths from the root node form complete words.

For example, if we insert:

hello
hi

The words share the starting character h, so the Trie avoids storing repeated prefixes again and again.

Trie vs HashMap

A HashMap can also be used to store words.

For example:

HashMap<String, Boolean> map = new HashMap<>();
map.put("hello", true);
map.put("hi", true);

This is good when we only want to check whether a complete word exists or not.

But a Trie is different because it stores words by characters and shared prefixes.

HashMap Approach

In a HashMap, each complete word is stored as one full key:

hello
hi
world

Searching a complete word is usually very fast, around O(1) on average.

But prefix-related operations are not natural in a HashMap.

For example, if we want all words starting with:

he

then with a HashMap, we may need to scan many stored words and check each one manually.

Trie Approach

In a Trie, words are stored character by character:

h -> e -> l -> l -> o
|
i

So prefixes are naturally represented as paths.

If we want to find words starting with "he", we first go to the node for "he", and then print all words below that node.

How Trie Has an Edge Over HashMap

Trie has an advantage over HashMap when the problem involves prefixes.

Trie is better for:

• Autocomplete systems
• Dictionary word search
• Prefix matching
• Spell checking
• Printing words in sorted order
• Finding all words with a given prefix

Example:

Words: hello, help, helper, hi
Prefix: hel

A Trie can directly reach the prefix path:

h -> e -> l

Then it can explore below that node to find:

hello
help
helper

With a HashMap, we would usually need to check every word and ask:

word.startsWith("hel")

So for prefix-based tasks, Trie is more suitable and more structured.

When HashMap is Better

HashMap is still better when we only need simple exact-word lookup.

For example:

map.containsKey("hello");

This is usually faster and simpler than using a Trie if we do not care about prefixes.

So the simple comparison is:

Requirement	Better Choice
Exact word search only	HashMap
Prefix search	Trie
Autocomplete	Trie
Sorted word traversal	Trie
Simple key-value storage	HashMap

TrieNode Structure

Each TrieNode stores:

char data;
TrieNode children[];
boolean isTerminal;
int childCnt;

Meaning:

• data stores the character of the node.
• children stores links to the next possible characters.
• isTerminal tells whether a complete word ends at this node.
• childCnt stores how many children the node currently has.

The children array has size 26, so this implementation supports lowercase English letters from a to z.

Trie Class Responsibilities

The Trie class manages the complete Trie data structure.

It contains:

• A private root node.
• A method to add words.
• A method to search words.
• A method to remove words.
• A method to print all stored words.

Operations Implemented

1. Add a Word

trie.add("hello");

The add() method inserts a word into the Trie.

It starts from the root and creates missing nodes for each character. At the end of the word, it marks the final node as terminal.

2. Search a Word

trie.search("hello");

The search() method checks whether a complete word exists in the Trie.

It returns:

• true if the complete word is present.
• false if the word is missing or only exists as a prefix.

For example:

trie.add("hello");

trie.search("hello"); // true
trie.search("he");    // false

Here, "he" returns false because it is only a prefix, not a complete inserted word.

3. Remove a Word

trie.remove("hello");

The remove() method unmarks the terminal node of the word.

After that, it also removes unnecessary nodes if:

• The node is not the end of another word.
• The node has no children.

The childCnt variable helps remove unused nodes efficiently.

4. Print All Words

trie.print();

The print() method prints all complete words stored in the Trie.

It uses recursion to visit every possible path from the root.

Example Usage

From TrieUse.java:

public class TrieUse {
    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.add("hello");
        trie.add("world");
        trie.add("hi");

        System.out.println(trie.search("hello")); // true
        System.out.println(trie.search("world")); // true
        System.out.println(trie.search("hi"));    // true
        System.out.println(trie.search("he"));    // false

        trie.print();
    }
}

Sample Output

true
true
true
false
hello
hi
world

Time Complexity

Let L be the length of the word.

Operation	Time Complexity
Add word	O(L)
Search word	O(L)
Remove word	O(L)
Print all words	O(total characters stored)

Each add, search, and remove operation depends on the length of the word, not on the total number of words stored.

Space Complexity

The space complexity depends on the number of unique characters stored in the Trie.

In the worst case, if no words share prefixes, more nodes are created.

If many words share prefixes, the Trie saves space by reusing common paths.

How to Compile and Run

Compile:

javac Trie.java TrieUse.java

Run:

java TrieUse

Key Points

• Trie is useful for prefix-based word storage.
• Each node stores one character.
• isTerminal marks the end of a complete word.
• childCnt helps during deletion.
• TrieNode is kept with the Trie implementation in Trie.java for simplicity.

👨‍💻 Author

Mrutunjaya Panda

⭐ Support

If you found this useful, give it a ⭐ and feel free to fork!