How to implement a Trie data structure in Java?
Jul 13, 2025 am 01:16 AMThe core of implementing the Trie tree is to design the node structure and correctly handle the insertion and search logic. 1. The TrieNode class contains a character array or hash table to indicate whether the child nodes and markers are endings; 2. Insert operation to build a character-by-character path and mark the end of the word at the end; 3. The search operation is divided into two situations: complete word matching and prefix matching; 4. It is necessary to consider edge cases such as empty strings, case sensitivity, memory optimization, etc. and improvement directions.
Implementing a trie (prefix tree) in Java is a common task when dealing with problems related to string searching, autocomplete features, or dictionary implementations. The core idea behind a trie is that each node represents a character, and paths from the root to nodes represent possible strings.

Basic Structure of a Trie Node
To start building a trie, you first need a TrieNode
class. This class will represent each character in the trie and contain:
- An array or map of children (dependent on whether you're using a fixed alphabet like lowercase English letters or a more general approach).
- A flag to indicate if the node marks the end of a word.
class TrieNode { private TrieNode[] children; private boolean isEndOfWord; private static final int ALPHABET_SIZE = 26; // assuming only lowercase English letters public TrieNode() { children = new TrieNode[ALPHABET_SIZE]; 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; } }
Using an array here makes looksups faster since we can directly index into the correct position using ch - 'a'
. If you expect other characters (like uppercase or symbols), consider using a HashMap<Character, TrieNode>
instead.

Inserting Words into the Trie
Insertion involves going through each character of the word and adding nodes as needed. Start at the root node and for each character:
- If the child node doesn't exist, create it.
- Move to the child node.
- At the end of the word, mark the last node as the end of a word.
Here's how that looks in code:

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); } }
This ensures that all words are stored efficiently and overlapping prefixes are shared among different words.
Searching for Words or Prefixes
Searching works similarly to insertion but stops early if a character isn't found. There are two main cases:
- Exact word match – requires reaching the end of the word and checking if
isEndOfWord
is true. - Prefix search – just checks whether the path exists, regardless of
isEndOfWord
.
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(); // Only return true if it's marked as end of a word } public boolean startsWith(String prefix) { TrieNode current = root; for (char ch : prefix.toCharArray()) { current = current.getChild(ch); if (current == null) { return false; } } return true; }
These methods make it easy to support both exact searches and autocomplete-style suggestions.
Handling Edge Cases and Improvements
A few edge cases are worth considering:
- Empty strings: You might want to decide whether to allow them or not.
- Case sensitivity: Convert input to lowercase before processing unless you want case-sensitive behavior.
- Memory optimization: For large datasets, consider compressing the trie or switching to a ternary search tree.
Also, if you're planning to implement deletion later, keep track of how many words use each node so you know when it's safe to remove one.
So, implementing a basic trie in Java boils down to creating a proper node structure and carefully handling insertion and lookup logic. It's not too complicated once you get the structure right, but small mistakes — like forgetting to mark the end of a word — can cause bugs that are tricky to trace.
Basically that's it.
The above is the detailed content of How to implement a Trie data structure in Java?. For more information, please follow other related articles on the PHP Chinese website!

Hot AI Tools

Undress AI Tool
Undress images for free

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

Singleton design pattern in Java ensures that a class has only one instance and provides a global access point through private constructors and static methods, which is suitable for controlling access to shared resources. Implementation methods include: 1. Lazy loading, that is, the instance is created only when the first request is requested, which is suitable for situations where resource consumption is high and not necessarily required; 2. Thread-safe processing, ensuring that only one instance is created in a multi-threaded environment through synchronization methods or double check locking, and reducing performance impact; 3. Hungry loading, which directly initializes the instance during class loading, is suitable for lightweight objects or scenarios that can be initialized in advance; 4. Enumeration implementation, using Java enumeration to naturally support serialization, thread safety and prevent reflective attacks, is a recommended concise and reliable method. Different implementation methods can be selected according to specific needs

ThreadLocal is used in Java to create thread-private variables, each thread has an independent copy to avoid concurrency problems. It stores values ??through ThreadLocalMap inside the thread. Pay attention to timely cleaning when using it to prevent memory leakage. Common uses include user session management, database connections, transaction context, and log tracking. Best practices include: 1. Call remove() to clean up after use; 2. Avoid overuse; 3. InheritableThreadLocal is required for child thread inheritance; 4. Do not store large objects. The initial value can be set through initialValue() or withInitial(), and the initialization is delayed until the first get() call.

Analyzing Java heap dumps is a key means to troubleshoot memory problems, especially for identifying memory leaks and performance bottlenecks. 1. Use EclipseMAT or VisualVM to open the .hprof file. MAT provides Histogram and DominatorTree views to display the object distribution from different angles; 2. sort in Histogram by number of instances or space occupied to find classes with abnormally large or large size, such as byte[], char[] or business classes; 3. View the reference chain through "ListObjects>withincoming/outgoingreferences" to determine whether it is accidentally held; 4. Use "Pathto

Optional can clearly express intentions and reduce code noise for null judgments. 1. Optional.ofNullable is a common way to deal with null objects. For example, when taking values ??from maps, orElse can be used to provide default values, so that the logic is clearer and concise; 2. Use chain calls maps to achieve nested values ??to safely avoid NPE, and automatically terminate if any link is null and return the default value; 3. Filter can be used for conditional filtering, and subsequent operations will continue to be performed only if the conditions are met, otherwise it will jump directly to orElse, which is suitable for lightweight business judgment; 4. It is not recommended to overuse Optional, such as basic types or simple logic, which will increase complexity, and some scenarios will directly return to nu.

The core workaround for encountering java.io.NotSerializableException is to ensure that all classes that need to be serialized implement the Serializable interface and check the serialization support of nested objects. 1. Add implementsSerializable to the main class; 2. Ensure that the corresponding classes of custom fields in the class also implement Serializable; 3. Use transient to mark fields that do not need to be serialized; 4. Check the non-serialized types in collections or nested objects; 5. Check which class does not implement the interface; 6. Consider replacement design for classes that cannot be modified, such as saving key data or using serializable intermediate structures; 7. Consider modifying

ToimproveperformanceinJavaapplications,choosebetweenEhCacheandCaffeinebasedonyourneeds.1.Forlightweight,modernin-memorycaching,useCaffeine—setitupbyaddingthedependency,configuringacachebeanwithsizeandexpiration,andinjectingitintoservices.2.Foradvance

There are three common ways to parse JSON in Java: use Jackson, Gson, or org.json. 1. Jackson is suitable for most projects, with good performance and comprehensive functions, and supports conversion and annotation mapping between objects and JSON strings; 2. Gson is more suitable for Android projects or lightweight needs, and is simple to use but slightly inferior in handling complex structures and high-performance scenarios; 3.org.json is suitable for simple tasks or small scripts, and is not recommended for large projects because of its lack of flexibility and type safety. The choice should be decided based on actual needs.

Serialization is the process of converting an object into a storageable or transferable format, while deserialization is the process of restoring it to an object. Implementing the Serializable interface in Java can use ObjectOutputStream and ObjectInputStream to operate. 1. The class must implement the Serializable interface; 2. All fields must be serializable or marked as transient; 3. It is recommended to manually define serialVersionUID to avoid version problems; 4. Use transient to exclude sensitive fields; 5. Rewrite readObject/writeObject custom logic; 6. Pay attention to security, performance and compatibility
