Trie map - trie implementation using hashmap

What is a trie map?

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. A trie map is a trie that uses a hashmap in the trie node that used to access child nodes.

How is a hashmap used in a trie node?

In a trie, 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. The data structure can be an array, a linked list, or a hash map. When the data structure is a hash map, the character is the key to finding the corresponding node in the branch. Using a hash map is better than an array since it minimizes unnecessary memory space.

Table of Content

Map of trie implementations

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

you are here

Part 3 – trie implementation using a 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, children, and isEnd. data stores a character. children is a data structure that stores the references to child nodes (branches). Here the data structure is a hash map. isEnd is to mark whether this is the last node in the branch.

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

import java.util.*;

public class TrieMap {
	
	class TrieNode {
		 char data;
		 HashMap<Character, TrieNode> children = new HashMap<>();     
		 boolean isEnd = false;
 		 
		//Constructor, Time O(1), Space O(1)
		 TrieNode(char c) {
			 this.data = c;
		 }
	}

	TrieNode root = new TrieNode(' ');

import java.util.*;

public class TrieMap {

class TrieNode {

char data;

HashMap<Character, TrieNode> children = new HashMap<>();

boolean isEnd = false;

//Constructor, Time O(1), Space O(1)

TrieNode(char c) {

this.data = c;

}

TrieNode root = new TrieNode(' ');

Javascript

class TrieNode {

    //Constructor, Time O(1), Space O(1)
    constructor(c) {
        this.data = c;
        this.isEnd = false;
        this.children = new Map(); //map
    }
}
  
class Trie {
    //Constructor, Time O(1), Space O(1)
    constructor() {
        this.root = new TrieNode('');
    }

class TrieNode {

//Constructor, Time O(1), Space O(1)

constructor(c) {

this.data = c;

this.isEnd = false;

this.children = new Map(); //map

}

class Trie {

//Constructor, Time O(1), Space O(1)

constructor() {

this.root = new TrieNode('');

}

Python

class TrieNode:

    #constructor, Time O(1) Space O(1)
    def __init__(self, c):
        self.data = c
        self.isEnd = False
        self.children = {} #map

class Trie:
    #constructor, Time O(1) Space O(1)
    def __init__(self):
        self.root = TrieNode('')

class TrieNode:

#constructor, Time O(1) Space O(1)

def __init__(self, c):

self.data = c

self.isEnd = False

self.children = {} #map

class Trie:

#constructor, Time O(1) Space O(1)

def __init__(self):

self.root = TrieNode('')

Insert a string in trie implementation

To insert a string, first check whether the string is in the trie so that you don’t insert a duplicate string. You start at root and loop through each character in the string. Create a new node “newNode” to store the character “ch”. Add the (ch, newNode) pair as an entry to the node’s children. Then move on to the next character and so on. When the node contains the last character of the string, you mark the node’s isEnd to be true.

Java

	//Add a word to trie, Iteration, Time O(s), Space O(s), s is word length
	void insert(String word) {
		if (search(word) == true) {
			System.out.println(word + " is already in trie.");
			return;
		} 
		TrieNode node = root;
		for (char ch : word.toCharArray()) {
			if (!node.children.containsKey(ch)) 
				node.children.put(ch, new TrieNode(ch));			         			    
			node = node.children.get(ch);	
		}
		node.isEnd = true;	
	}

//Add a word to trie, Iteration, Time O(s), Space O(s), s is word length

void insert(String word) {

if (search(word) == true) {

System.out.println(word + " is already in trie.");

return;

}

TrieNode node = root;

for (char ch : word.toCharArray()) {

if (!node.children.containsKey(ch))

node.children.put(ch, new TrieNode(ch));

node = node.children.get(ch);

}

node.isEnd = true;

}

Javascript

    //inserts a word into the trie. Time O(s), Space O(s), s is word length
    insert (word) {
        if (this.search(word) == true) {
            System.out.println(word + " is already in trie.");
            return;
        } 
        var node = this.root;
        for (let ch of word) {
            if (!node.children.has(ch)) 
                node.children.set(ch, new TrieNode(ch));           
            node = node.children.get(ch);        
        }
        node.isEnd = true;
    }

//inserts a word into the trie. Time O(s), Space O(s), s is word length

insert (word) {

if (this.search(word) == true) {

System.out.println(word + " is already in trie.");

return;

}

var node = this.root;

for (let ch of word) {

if (!node.children.has(ch))

node.children.set(ch, new TrieNode(ch));

node = node.children.get(ch);

}

node.isEnd = true;

}

Python

    #Add a word to trie, Time O(s) Space O(s), s is word length
    def insert(self, word):
        if self.search(word) == True:
            print(word + " is already in trie.")
            return  
        node = self.root
        for ch in word:
            if not ch in node.children:
                node.children[ch] = TrieNode(ch)   
            node = node.children[ch]                 
        node.isEnd = True

#Add a word to trie, Time O(s) Space O(s), s is word length

def insert(self, word):

if self.search(word) == True:

print(word + " is already in trie.")

return

node = self.root

for ch in word:

if not ch in node.children:

node.children[ch] = TrieNode(ch)

node = node.children[ch]

node.isEnd = True

Doodle

trie insert array

Delete a string

To delete a string from a trie, first check whether the string exists in the trie. If not, the method can return. Otherwise, you start at root and loop through each character in the string. If the character is in the node’s children’s key set, move on to the child node. When the node has the last character of the string, mark the node’s isEnd to be false. The string is still in the trie, but unsearchable.

Java

	//Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length
	void delete(String word) {	 
		if (this.search(word) == false) {
			System.out.println(word + " does not exist in trie.");
			return;
		}
		TrieNode node = root;
		for (char ch : word.toCharArray()) {        	
			if (!node.children.containsKey(ch)) 
				return;	        
			node = node.children.get(ch);	            
		}
		node.isEnd = false; 
	}

//Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length

void delete(String word) {

if (this.search(word) == false) {

System.out.println(word + " does not exist in trie.");

return;

}

TrieNode node = root;

for (char ch : word.toCharArray()) {

if (!node.children.containsKey(ch))

return;

node = node.children.get(ch);

}

node.isEnd = false;

}

Javascript

    //Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length
    delete(word) {	 
        if (this.search(word) == null) {
            console.log(word + " does not exist in trie.");
            return;
        }    
        let node = this.root;
        for (let ch of word) {
            if (!node.children.has(ch)) 
                return;
            node = node.children.get(ch);
        }
        node.isEnd = false;  
    }

//Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length

delete(word) {

if (this.search(word) == null) {

console.log(word + " does not exist in trie.");

return;

}

let node = this.root;

for (let ch of word) {

if (!node.children.has(ch))

return;

node = node.children.get(ch);

}

node.isEnd = false;

}

Python

    #Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length
    def delete(self, word):
        if self.search(word) == False:
            print(word + " does not exist in trie.")
            return
        node = self.root
        for ch in word: 
            if not ch in node.children:
                return
            node = node.children.get(ch)    
        node.isEnd = False

#Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length

def delete(self, word):

if self.search(word) == False:

print(word + " does not exist in trie.")

return

node = self.root

for ch in word:

if not ch in node.children:

return

node = node.children.get(ch)

node.isEnd = False

Search a string

To search for a string in a trie, start at root and loop through each character in the string. If the character is not in the node’s children’s key set, the method returns false. Otherwise, move on to the child node. When the node has the last character of the string, return the node’s isEnd value. If the value is false, it indicates the string has been deleted.

Java

	//Search a word in trie, Iteration, Time O(s), Space O(1), s is word length
	boolean search(String word) {
		TrieNode node = root;
		for (char ch : word.toCharArray()) {
			if (!node.children.containsKey(ch)) 
				return false;		        
			node = node.children.get(ch);
		}
		return node.isEnd;
	}

//Search a word in trie, Iteration, Time O(s), Space O(1), s is word length

boolean search(String word) {

TrieNode node = root;

for (char ch : word.toCharArray()) {

if (!node.children.containsKey(ch))

return false;

node = node.children.get(ch);

}

return node.isEnd;

}

Javascript

    //Search a word in trie, Iteration, Time O(s), Space O(1), s is word length
    search(word) {
        let node = this.root;
        for(let ch of word) {
            if (!node.children.has(ch)) 
                return false;
            node = node.children.get(ch);        
        }   
        return node.isEnd;
    }

//Search a word in trie, Iteration, Time O(s), Space O(1), s is word length

search(word) {

let node = this.root;

for(let ch of word) {

if (!node.children.has(ch))

return false;

node = node.children.get(ch);

}

return node.isEnd;

}

Python

    #Search a word in trie, Iteration, Time O(s), Space O(1), s is word length
    def search(self, word):
        node = self.root
        for ch in word:           
            if not ch in node.children:
                return False
            node = node.children.get(ch)
        return node.isEnd

#Search a word in trie, Iteration, Time O(s), Space O(1), s is word length

def search(self, word):

node = self.root

for ch in word:

if not ch in node.children:

return False

node = node.children.get(ch)

return node.isEnd

Print all strings in a trie

To print all strings in a trie, recursion is used to traverse all nodes in the trie. This is similar to the preorder (depth-first search) traversal of a 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 string. It indicates the completion of concatenating one string. You can go ahead to add the string to the result list.

Java

	//Print all words in trie, call recursion function
	//Time O(n), Space O(n), n is number of nodes in trie
	void print() {
		List<String> res = new ArrayList<String>(); 
		helper(root, res, "");
		System.out.println(res);
	}
	
	//recursive function, Time O(n), Space O(n), n is number of nodes in trie
	void helper(TrieNode node, List<String> res, String prefix) {
		if (node.isEnd) {
			String word = prefix + node.data;
			res.add(word.substring(1)); //skip the first space from root	
		}
		for (Character ch : node.children.keySet()) 
			helper(node.children.get(ch), res, prefix + node.data);
	}

//Print all words in trie, call recursion function

//Time O(n), Space O(n), n is number of nodes in trie

void print() {

List<String> res = new ArrayList<String>();

helper(root, res, "");

System.out.println(res);

}

//recursive function, Time O(n), Space O(n), n is number of nodes in trie

void helper(TrieNode node, List<String> res, String prefix) {

if (node.isEnd) {

String word = prefix + node.data;

res.add(word.substring(1)); //skip the first space from root

}

for (Character ch : node.children.keySet())

helper(node.children.get(ch), res, prefix + node.data);

}

Javascript

    //Print all words in trie, call recursion function
	//Time O(n), Space O(n), n is number of nodes in trie
    print() {
        let res = [];
        this.helper(this.root, res, "");
        console.log(res);
    }

    //recursion function, Time O(n), Space O(n), n is number of nodes in trie
    helper (node, arr, perfix) {
        if (node.isEnd)
            arr.push(perfix + node.data);
        for (let c of node.children.keys()) 
            this.helper(node.children.get(c), arr, perfix + node.data);
    }

//Print all words in trie, call recursion function

//Time O(n), Space O(n), n is number of nodes in trie

print() {

let res = [];

this.helper(this.root, res, "");

console.log(res);

}

//recursion function, Time O(n), Space O(n), n is number of nodes in trie

helper (node, arr, perfix) {

if (node.isEnd)

arr.push(perfix + node.data);

for (let c of node.children.keys())

this.helper(node.children.get(c), arr, perfix + node.data);

}

Python

    #Print all words in trie, call recursion function
	#Time O(n), Space O(n), n is number of nodes in trie
    def print(self):
        res = []
        self.helper(self.root,res, "") 
        print(res)

	#recursion function, Time O(n), Space O(n), n is number of nodes in trie
    def helper(self, node, res, prefix):
        if node.isEnd:
            res.append(prefix + node.data)       
        for child in node.children.values():
            self.helper(child, res, prefix + node.data)

#Print all words in trie, call recursion function

#Time O(n), Space O(n), n is number of nodes in trie

def print(self):

res = []

self.helper(self.root,res, "")

print(res)

#recursion function, Time O(n), Space O(n), n is number of nodes in trie

def helper(self, node, res, prefix):

if node.isEnd:

res.append(prefix + node.data)

for child in node.children.values():

self.helper(child, res, prefix + node.data)

Free download

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

Login

Trie map – trie implementation using a hashmap

What is a trie map?

How is a hashmap used in a trie node?

Table of Content

Map of trie implementations

Define classes in trie implementation

Java

Javascript

Python

Insert a string in trie implementation

Java

Javascript

Python

Doodle

Delete a string

Java

Javascript

Python

Search a string

Java

Javascript

Python

Print all strings in a trie

Java

Javascript

Python

Free download