Back to Course

0% Complete
0/0 Steps

Lesson 23 of 48
In Progress

# Trie Trees in Java

A Trie tree is a type of data structure used to store and retrieve data in an efficient manner. It is an advanced form of a tree data structure, which organizes data into a hierarchy of parent-child relationships. The Trie tree is particularly useful for storing and retrieving strings of characters. In this article, we will discuss how a Trie tree works, its time and space complexity for various operations, and how to use it in Java.

## What is a Trie Tree?

A Trie tree is a specialized tree used to store strings of characters. It is composed of nodes, which represent a single character in the string. Each node is linked to its parent and child nodes, forming a hierarchy. The root node is the start of the tree and has no parent node. Each subsequent node is linked to its parent and children nodes, forming a tree-like structure.

The trie tree is an efficient data structure for storing and retrieving strings. It is optimized for searching for strings of characters, and can be used for a variety of tasks such as:

• Spell checking
• Autocompletion
• Pattern matching
• Text search
• Dictionary operations

## Time Complexity

The time complexity of a Trie tree is dependent on the number of characters in the string being stored.

### Searching

Searching a Trie tree has an average time complexity of O(m), where m is the number of characters in the input string. In the worst case, the time complexity is O(n), where n is the number of nodes in the tree.

### Insertion

Inserting a string into a Trie tree has an average time complexity of O(m), where m is the number of characters in the string. In the worst case, the time complexity is O(n), where n is the number of nodes in the tree.

### Deletion

Deleting a string from a Trie tree has an average time complexity of O(m), where m is the number of characters in the string. In the worst case, the time complexity is O(n), where n is the number of nodes in the tree.

### Space Complexity

The space complexity of a Trie tree is dependent on the number of strings being stored. The worst case space complexity is O(n*m), where n is the number of nodes and m is the number of characters in the longest string.

## Using Trie Trees in Java

Now that we have discussed the time and space complexity of a Trie tree, let us look at how to implement one in Java.

### Creating a Trie Tree

The following class creates a TrieNode, which will be the basis of the Trie tree. The TrieNode class stores the characters stored in the Trie tree, as well as a boolean indicating whether the node is the end of a string.

public class TrieNode {
char data;
boolean isEndOfString;
TrieNode[] children;

public TrieNode(char data) {
this.data = data;
this.isEndOfString = false;
this.children = new TrieNode;
}
}

The following class creates the Trie tree. The Trie class stores the root node of the Trie tree, and provides methods for searching, insertion, and deletion.

public class Trie {
TrieNode root;

public Trie() {
root = new TrieNode(' ');
}

//Search a string in the trie
public boolean search(String str) {
//Start from the root node
TrieNode currentNode = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
//Check if the character exists in the node
if (currentNode.children[index] == null) {
return false;
}
currentNode = currentNode.children[index];
}
//Check if the last node is the end of a string
return currentNode.isEndOfString;
}

//Insert a string in the trie
public void insert(String str) {
//Start from the root node
TrieNode currentNode = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
//Check if the character exists in the node
if (currentNode.children[index] == null) {
currentNode.children[index] = new TrieNode(c);
}
currentNode = currentNode.children[index];
}
//Mark the last node as the end of a string
currentNode.isEndOfString = true;
}

//Delete a string from the trie
public void delete(String str) {
//Start from the root node
TrieNode currentNode = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
//Check if the character exists in the node
if (currentNode.children[index] == null) {
return;
}
currentNode = currentNode.children[index];
}
//Mark the last node as not the end of a string
currentNode.isEndOfString = false;
}
}

## Conclusion

In this article, we discussed how a Trie tree works, its time and space complexity for various operations, and how to use it in Java. The Trie tree is an optimized tree data structure for searching for strings of characters, and can be used for a variety of tasks such as spell checking, autocompletion, pattern matching, text search, and dictionary operations. The time complexity for searching, insertion, and deletion is O(m), where m is the number of characters in the input string. The space complexity is O(n*m), where n is the number of nodes and m is the number of characters in the longest string.

## Exercises

#### Create a class to implement a Trie tree in Java.

public class Trie {
TrieNode root;

public Trie() {
root = new TrieNode(' ');
}

//Search a string in the trie
public boolean search(String str) {
//Start from the root node
TrieNode currentNode = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
//Check if the character exists in the node
if (currentNode.children[index] == null) {
return false;
}
currentNode = currentNode.children[index];
}
//Check if the last node is the end of a string
return currentNode.isEndOfString;
}

//Insert a string in the trie
public void insert(String str) {
//Start from the root node
TrieNode currentNode = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
//Check if the character exists in the node
if (currentNode.children[index] == null) {
currentNode.children[index] = new TrieNode(c);
}
currentNode = currentNode.children[index];
}
//Mark the last node as the end of a string
currentNode.isEndOfString = true;
}

//Delete a string from the trie
public void delete(String str) {
//Start from the root node
TrieNode currentNode = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
//Check if the character exists in the node
if (currentNode.children[index] == null) {
return;
}
currentNode = currentNode.children[index];
}
//Mark the last node as not the end of a string
currentNode.isEndOfString = false;
}
}

#### Implement a method to search for a string in a Trie tree.

public boolean search(String str) {
//Start from the root node
TrieNode currentNode = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
//Check if the character exists in the node
if (currentNode.children[index] == null) {
return false;
}
currentNode = currentNode.children[index];
}
//Check if the last node is the end of a string
return currentNode.isEndOfString;
}


#### Implement a method to insert a string into a Trie tree.

public void insert(String str) {
//Start from the root node
TrieNode currentNode = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
//Check if the character exists in the node
if (currentNode.children[index] == null) {
currentNode.children[index] = new TrieNode(c);
}
currentNode = currentNode.children[index];
}
//Mark the last node as the end of a string
currentNode.isEndOfString = true;
}

#### Implement a method to delete a string from a Trie tree.

public void delete(String str) {
//Start from the root node
TrieNode currentNode = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
//Check if the character exists in the node
if (currentNode.children[index] == null) {
return;
}
currentNode = currentNode.children[index];
}
//Mark the last node as not the end of a string
currentNode.isEndOfString = false;
}

#### Implement a method to traverse a Trie tree.

public void traverseTrie(TrieNode node) {
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
System.out.print(node.children[i].data);
traverseTrie(node.children[i]);
}
}
}