### Introduction to Trie Data Structure - The Coding Shala

In this post, we will learn what is Trie Data Structure and how to implement Trie in Java.

## Introduction to Trie Data Structure

Trie is a special form of an N-ary tree, also called prefix tree. Tries are an extremely special and useful data-structure are based on the prefix of a string. They are used to represent the Retrieval of data and thus the name Trie.

A Trie is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of at max 26 children and edges connect each parent to its children. These 26 pointers are nothing but pointers for each of the 26 letters of the English alphabet.

Note: Root node is null in Trie.

Strings are stored in a top to bottom manner on the basis of their prefix in a trie. All prefixes of length 1 are stored until level 1, all prefixes of length 2 are sorted until level 2, and so on.

In the above example, if we start from the root node and choose the second path 'b' then choose the first child 'a' and choose child 'd' then we finally make the string "bad".

One important property of Trie is that all the descendants of a node have a common prefix of the string associated with that node. That's why Trie is also called prefix tree.

**Now the question comes to mind how do we represent Trie?**

We can use the array to store children nodes. We can declare an array whose size is 26 in each node to store its children nodes. The following code explains it:

class TrieNode{ public static final N = 26; public TrieNode[] children = new TrieNode[N]; }

The second method is to use a hashMap to store children nodes. We can declare a hashMap in each node. The key of the hashMap are children and the value is the corresponding child node.

The following code explains it:

class TrieNode{ public Map<Character, TrieNode> children = new HashMap<>(); }

#### Insertion in Trie

#### Search in Trie

### Basic Implementation of Trie Data Structure

**Example:**

## Java Program to Implement Trie using Array

class TrieNode{ boolean isEndOfWord; TrieNode[] children; TrieNode(){ this.isEndOfWord = false; this.children = new TrieNode[26]; } } class Trie { TrieNode root; /** Initialize your data structure here. */ public Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ public void insert(String word) { TrieNode curr = root; for(char ch : word.toCharArray()){ if(curr.children[ch-'a'] == null){ curr.children[ch-'a'] = new TrieNode(); } curr = curr.children[ch-'a']; } curr.isEndOfWord = true; } /** Returns if the word is in the trie. */ public boolean search(String word) { TrieNode curr = root; for(char ch : word.toCharArray()){ if(curr.children[ch-'a']==null){ return false; } curr = curr.children[ch-'a']; } if(curr.isEndOfWord) return true; return false; } /** Returns if there is any word in the trie that starts with the given prefix. */ public boolean startsWith(String prefix) { TrieNode curr = root; for(char ch : prefix.toCharArray()){ if(curr.children[ch-'a']==null){ return false; } curr = curr.children[ch-'a']; } return true; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */

## Java Program to Implement Trie using HashMap

class TrieNode{ Map<Character, TrieNode> child; boolean isEndOfWord; TrieNode(){ this.child = new HashMap<Character, TrieNode>(); this.isEndOfWord = false; } } class Trie { TrieNode root; /** Initialize your data structure here. */ public Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ public void insert(String word) { TrieNode curr = root; for(char ch : word.toCharArray()){ if(!curr.child.containsKey(ch)){ curr.child.put(ch, new TrieNode()); } curr = curr.child.get(ch); } curr.isEndOfWord = true; } /** Returns if the word is in the trie. */ public boolean search(String word) { TrieNode curr = root; for(char ch : word.toCharArray()){ if(!curr.child.containsKey(ch)){ return false; } curr = curr.child.get(ch); } if(curr.isEndOfWord) return true; return false; } /** Returns if there is any word in the trie that starts with the given prefix. */ public boolean startsWith(String prefix) { TrieNode curr = root; for(char ch : prefix.toCharArray()){ if(!curr.child.containsKey(ch)){ return false; } curr = curr.child.get(ch); } return true; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */

**Other Posts You May Like**

- Introduction to Binary Tree
- Introduction to Binary Search Tree
- Introduction to N-ary Tree
- Search in a Binary Search Tree
- Delete Node in a Binary Search Tree

## Comments

## Post a Comment