A trie is a tree-like data structure in which every node stores a character. It can store multiple words. 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. Here trie is implemented in Java, Python and JavaScript.

trie diagram

Each trie node might have multiple branches. So there is a data structure used to point to next nodes in branches. The 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.

Table of Content


Map of trie implementations

you are here

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


Define classes in trie implementation

Like building a tree, you need to define a TrieNode class before a Trie class. A TrieNode class has three variables: data stores a character, children is a data structure that points to children (branches) nodes. The data structure is an array. If you use only alphabet a-z, the length of the array is 26.  Here you define the array length to be 128 so that it can hold most ASCII characters; isEnd is to mark whether this is the last node in this branch (i.e. the last letter in the word). In Trie class, there is one class variable root. The operation of insertion, search or deletion always starts from root.

Java

Javascript

Python


Insert a word in trie implementation

To insert a word, first check whether the word is in the trie so that you don’t insert a duplicate word. Start from root, loop through each character in the word. Use the next character as the index to find the cell in the current node’s children, create a child node to store the next character and store the node in this cell. Then move to the child node. When it is the last character of the word, you mark the node‘s isEnd to be true.

Java

Javascript

Python

Doodle

trie insert array


Delete a word

To delete a word from the trie, first check whether the word exists in the trie. If not, the method can return. Otherwise, continue. The same as insertion, start from root. loop through each character in the word. If the next character is not in the node‘s children, the method returns directly. Otherwise, move to the child node. When it is the last character of the word, mark the node‘s isEnd to be false. The word is not actually deleted from the trie. It just becomes inaccessible.

Java

Javascript

Python

To search a word in the trie, start from root and loop through each character in the word. If the next character is not in the node‘s children, the method returns false. Otherwise, move to the child node. When it is the last character of the word, return the node‘s isEnd value, which can be true or false (deleted).

Java

Javascript

Python


Print all words in trie

This is to print all words in the trie. Similar to preorder (DFS, depth first search) 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 word. Add the word 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 point to next nodes in branches. The data structure to store child nodes can be an array, a linked list or a hash map.

How to implement a trie in Java?

Java doesn’t provide library (API) for trie. 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 find next nodes in branches from the current character. Then you define a Trie class. It has a root node. You insert a word by adding nodes from the first character to the last.