A trie is a tree-like data structure in which every node stores a character. After building the trie, strings or substrings can be retrieved by traversing down a path of the trie. Tries are used for find-substrings, auto-complete and many other string operations. Here trie implementation is done with Java, Python and JavaScript.

trie diagram


Table of Content


Map of trie implementations

In this post, the trie is implemented in hash map. The character is used as key to find the pointer to the child node.  Hash map is the best of three implementations since its put and get operations take O(1) time.

Part 1 – trie implementation using array
Part 2 – trie implementation using linked list

you are here

Part 3 – trie implementation using hash map


Define classes in trie implementation

The trie node class has three variables: data stores a character. children is a data structure that points to the children (branches) nodes. Here the data structure is hash map. isEnd is to mark whether this is the last node to compose a word. The trie class, there is one class level variable – root. The operation of insert, search or delete always starts from the 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 we don’t insert duplicate word. Then we loop through each character in the word. A pointer node starts from the root node. If the character is not in the node‘s children, a child node is created. Then the node moves to the child node. When the node is at the last character of the word, we 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. The same as insert, loop through each character in the word. A pointer node starts from the root node. If the character is not in the node‘s children, the method returns directly. Otherwise, the node moves to the child node. When the node is at the last character of the word, mark the node‘s isEnd to be false.

Java

Javascript

Python

To search a word in the trie, loop through each character in the word. A pointer node starts from the root node. If the character is not in the node‘s children, the method returns false. Otherwise, the node moves to the child node. When the node is at 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

To print all words in the trie, recursion is used to traverse all nodes in trie. This is similar to pre-order (DFS, depth first search) of the tree. When visiting the node, the method concatenates 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, and add the word to the result list.

Java

Javascript

Python


Free download

Download trie implementation using hashmap in Java, JavaScript and Python
Download aggregate Data Structures implementations in Java
Download aggregate Data Structures implementations in JavaScript
Download aggregate Data Structures implementations in Python

What are the children in the trie?

implement trie with map

A trie normally holds many words. Some characters might have multiple characters following it . For example, “ant”, “add”, “amy” share the same parent node ‘a’. The node ‘a’ has children of ‘n’, ‘d’ and ‘m’. So a trie is a n-ary tree. In the trie node, there is an attribute children, which holds the references to the nodes following it. The children can be  stored in a data structure such as array, linked list or hashmap.

What is time complexity of trie?

Insert a word in trie, search a word and delete a word by key all takes O(s) time, s is the length of the word.