This tutorial will introduce you to Trie data structure along with providing its implementation in Java.

Abstract

We all would have seen letter(character) based search in which results start to appear and refined as you type your search query. One of the best and popular example is Google search. Have you wondered how it works so fast especially when source data is so huge?

Trie data structure comes to rescue in these scenario although there is also an other variant called Suffix Tree that is more common. We will be covering Suffix tree in subsequent tutorials.

Note: Since Trie data structures are based on Tree data structures, it is recommended that you get yourself accustomed to Trees before proceeding with this tutorial.

What is Trie Data Structure?

Trie Data structure is a commonly used String comparison algorithm and is implemented by arranging letters of source String data into a Tree data structure. Suppose, we have few source strings as follows -

Welcome to All Programming Tutorials
Welcome to Trie Data Structure Tutorial
Trie Data Structure Implementation in Java

This is how it will look after adding it in Trie Data Structure -

Here are some of the points worth highlighting in above Trie data structure -

1. Root Node does not contain any data
2. All the branch of Trie end with # character (Any character that is not in source data can be used as end character). This makes searching and printing more convenient
3. Each of the node contains only a letter/character from source data
4. Each word in source data starts from Root Node. If a word's initial characters are same as others, it does not create a new branch and rather diverges from the same branch. E.g.. words Trie, Tutorial and Tutorials diverge from same branch starting with 'T'

After seeing Trie data structure in action, it should not be hard to realize its benefits. Some of its benefits are -

1. It makes word search faster as max time taken to search is time taken to search the word with max length. In our case, max time taken to search a word in our source string is same as time taken to iterate over 'Implementation' word
2. It also reduces the memory requirements in case words are frequently started with same characters as in these case, we utilize existing nodes rather than creating new ones

Trie Implementation in Java

Let's now talk about implementing Trie data structure. Trie implementation is quite simply and resembles Tree implementation. Trie data structure typically supports following operations -

1. Adding a sentence
2. Adding a word
3. Searching a word

Here is basic implementation of Trie data structure in Java -

package com.saintech.allprogtutorials.datastructures;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Sain Technology Solutions.
 * 
 * Trie Implementation in Java.
 */
public class JavaTrie {
	private static final char END_CHAR = '#';
	
	/**
	 * Represents Trie Node with its character and child nodes.
	 */
	private static class TrieNode{
		private final Character character;
		private final Map<TrieNode, TrieNode> childNodes = new HashMap<>();
		private TrieNode(Character character) {
			this.character = character;	
		}
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result
					+ ((character == null) ? 0 : character.hashCode());
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			TrieNode other = (TrieNode) obj;
			if (character == null) {
				if (other.character != null)
					return false;
			} else if (!character.equals(other.character))
				return false;
			return true;
		}
	}
	
	/** We will use empty space as root node. */
	private TrieNode root = new TrieNode(' ');
	
	/**
	 * Adds input sentence to Trie. Internally splits sentence into words and use addWord method 
	 * for adding each of words.
	 */
	public JavaTrie addSentence(String sentence) {
		final String[] words = sentence.split(" ");
		for(String word : words) {
			addWord(word);
		}
		return this;
	}
	
	/**
	 * Adds input word to Trie.
	 */
	public JavaTrie addWord(String word) {
		final char[] tokens = (word + END_CHAR).toCharArray();
		
		TrieNode tmpNode = root;
		for(char token : tokens) {
			TrieNode tokenNode = new TrieNode(token);
			if(tmpNode.childNodes.containsKey(tokenNode)) {
				tokenNode = tmpNode.childNodes.get(tokenNode);
			} else {
				tmpNode.childNodes.put(tokenNode, tokenNode);
			}
			tmpNode = tokenNode;
		}
		
		return this;
	}
	
	/**
	 * Checks whether Trie contains input word.
	 */
	public boolean containsWord(String word) {
		final char[] tokens = (word + END_CHAR).toCharArray();
		
		TrieNode tmpNode = root;
		for(char token : tokens) {
			final TrieNode tokenNode = new TrieNode(token);
			if(tmpNode.childNodes.containsKey(tokenNode)) {
				tmpNode = tmpNode.childNodes.get(tokenNode);
			} else {
				return false;
			}
		}
		
		return true;
	}
}

Above code also contains a nested class called TrieNode to represent a Node containing a character. We could have used Set to maintain child nodes but it does not provide get(elem) method. Hence Map with same key and value has been used.

Here is the demo class for testing above code -

package com.saintech.allprogtutorials.datastructures.demo;

import com.saintech.allprogtutorials.datastructures.JavaTrie;


/**
 * @author Sain Technology Solutions
 */
public class JavaTrieDemo {
	public static void main(String[] args) {
		final JavaTrie javaTrie = new JavaTrie();
		javaTrie.addWord("Welcome").addWord("To").addWord("All").addWord("Programming").addWord("Tutorials");
		System.out.println(javaTrie.containsWord("Programming"));
		System.out.println(javaTrie.containsWord("Tutorial"));
		
		final JavaTrie javaTrie1 = new JavaTrie();
		javaTrie1.addSentence("Welcome to All Programming Tutorials");
		javaTrie1.addSentence("Welcome to Trie Data Structure Tutorial");
		javaTrie1.addSentence("Trie Data Structure Implementation in Java");
		
		System.out.println(javaTrie1.containsWord("Programming"));
		System.out.println(javaTrie1.containsWord("Tutorial"));
	}
}

And this is the output that you will get after executing above two classes -

true
false
true
true

Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.