A trie is a tree-like data structure that can store multiple strings. A node in a trie stores a character. After building a trie, strings or substrings can be retrieved by traversing down a path (a branch) of the trie. Tries are used to find substrings, autocomplete, and many other string operations.

trie diagram

Each trie node might have multiple branches. So a trie node has a data structure to store the references to the next nodes in the branches. This data structure can be an array, a linked list, or a hash map. Using an array is the most intuitive implementation. This post is to introduce trie implementation using an array for the references to the next nodes.

Table of Content


Map of trie implementations

you are here

Part 1 – Trie implementation using an array.
Part 2 – Trie implementation using a linked list
Part 3 – Trie implementation using a hash map


Define classes in trie implementation

Like building a tree, we define a TrieNode class before a Trie class. A TrieNode class has three variables: data, children, and isEnd. data stores a character. children is a data structure that stores the references to the next nodes in the branches. The data structure is an array. If we use only the alphabet a-z, the length of the array is 26.  If the string has special symbols or characters, the array length is 128 or 256. isEnd is to mark whether this is the last node in this branch, i.e. the last character in the string.

In the Trie class, there is a variable root. The operation of insertion, search, or deletion always starts from root. The data of the root can be any character, which is not associated with any strings. Its children hold references to the first characters in strings.

Java

Javascript

Python


Insert a string in trie implementation

To insert a string, you start at root. For each character in the string, create a new node with the character as its data. Use the character as the index to find the cell in the array of children, and save the reference of the new node in that cell. Then move on to the newly created node. Once reaching the last character in the string, mark the node’s isEnd to be true.

Java

Javascript

Python

Doodle

trie insert array


Delete a string

To delete a string from the trie, first check whether the string exists in the trie. If not, the method can return. For each character in the string, examine if the node’s children have a value at the index of the character. If yes, use the character as the index to locate the corresponding node and move to that node. When reaching the last node, set the node’s isEnd to be false. The string is still in the trie, but unsearchable.

Java

Javascript

Python

To search a string in the trie, start from root and loop through each character in the string. If the node’s children don’t have a value at the index of the character, the method returns false. Otherwise, move to the child node by the reference stored in children. When reaching the last node in the branch, return the node’s isEnd value. If the value is false, it indicates the string has been deleted.

Java

Javascript

Python


Print all strings in a trie

This is to print all strings in the trie. Similar to the preorder (depth-first search) traversal of a tree, recursion is used to traverse all nodes in a trie. When visiting the node, concatenate characters from previously visited nodes with the character of the current node. When the node’s isEnd is true, the recursion reaches the last character of the string. It indicates the completion of concatenating one string. You can go ahead to add the string to the result list.

Java

Javascript

Python


Free download

Download trie implementation using Array in Java, JavaScript and Python
Data structures introduction PDF

What data structures are used to implement a trie?

In a trie, each trie node might have multiple branches. So there is a data structure used to store references to the next nodes in the branches. This data structure can be an array, a linked list, or a hash map.

How to implement a trie in Java?

You implement a trie just like building a tree. You define a TrieNode class first. It has a data structure called children, which is used to store the references to the next nodes in the branches. Then you define a Trie class. It has a root node. You insert a string by adding nodes from the first character to the last.