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. Insert a word in trie, search a word and delete a word by key all takes O(n) time, at the expense of storage.

Trie’s node can be implemented with array, linked list, HashMap. Each implementation has its pros and cons. Array is the most intuitive implementation. The character is used as index to find the pointer to the child node. However, each node needs to declare a predefined length of (number of characters) array. If you use only alphabet, the size is 26. If you use special characters such as space, the size is 128 or more. This takes memory space. This post is trie implemented using array.

trie diagram

you are here

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

Table of Content


Define classes

The trie node class has tree variables: data stores a character, children is a data structure that points to the children (branches) nodes (here the data structure is array); 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

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

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. The word is not actually deleted from the trie. It becomes invisible.

Java

Javascript

Python


Search

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

This is to print all words in the trie. Similar to pre-order (DFS, depth first search) of the tree, recursion is used to traverse all nodes in trie. 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. Add the word to the result list.

Java

Javascript

Python

Download Java, JavaScript and Python code
Trie animated visual
Data structures and Java collections