The trie data structure offers several advantages that make it a valuable choice in various scenarios:
There are three operations in the Trie:
class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26]; // Assuming lowercase English letters
isEndOfWord = false;
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
insertRecursive(root, word, 0);
}
private void insertRecursive(TrieNode node, String word, int index) {
// Base case: If all characters of the word are processed
if (index == word.length()) {
node.isEndOfWord = true;
return;
}
char currentChar = word.charAt(index);
int childIndex = currentChar - 'a';
// If the current character is not present in the trie, create a new node
if (node.children[childIndex] == null) {
node.children[childIndex] = new TrieNode();
}
// Recursively insert the remaining characters
insertRecursive(node.children[childIndex], word, index + 1);
}
}
class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26]; // Assuming lowercase English letters
isEndOfWord = false;
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public boolean search(String word) {
return searchRecursive(root, word, 0);
}
private boolean searchRecursive(TrieNode node, String word, int index) {
// Base case: If all characters of the word are processed
if (index == word.length()) {
return node.isEndOfWord;
}
char currentChar = word.charAt(index);
int childIndex = currentChar - 'a';
// If the current character is not present in the trie, the word does not exist
if (node.children[childIndex] == null) {
return false;
}
// Recursively search for the remaining characters
return searchRecursive(node.children[childIndex], word, index + 1);
}
}
class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26]; // Assuming lowercase English letters
isEndOfWord = false;
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void delete(String word) {
deleteRecursive(root, word, 0);
}
private boolean deleteRecursive(TrieNode node, String word, int index) {
// Base case: If all characters of the word are processed
if (index == word.length()) {
if (!node.isEndOfWord) {
// The word does not exist in the trie
return false;
}
node.isEndOfWord = false;
return isEmptyNode(node);
}
char currentChar = word.charAt(index);
int childIndex = currentChar - 'a';
// If the current character is not present in the trie, the word does not exist
if (node.children[childIndex] == null) {
return false;
}
boolean shouldDeleteChildNode = deleteRecursive(node.children[childIndex], word, index + 1);
// If child node should be deleted, remove the reference from the current node
if (shouldDeleteChildNode) {
node.children[childIndex] = null;
return isEmptyNode(node);
}
return false;
}
private boolean isEmptyNode(TrieNode node) {
// Check if the node has any non-null children
for (TrieNode child : node.children) {
if (child != null) {
return false;
}
}
return true;
}
}
Note: also read about Trees: Lowest Common Ancestor
If you like my post please follow me to read my latest post on programming and technology.
https://www.instagram.com/coderz.py/
https://www.facebook.com/coderz.py
Staying up to the mark is what defines me. Hi all! I’m Rabecca Fatima a keen learner, great enthusiast, ready to take new challenges as stepping stones towards flying colors.
Given an integer A. Compute and return the square root of A. If A is…
Given a zero-based permutation nums (0-indexed), build an array ans of the same length where…
A heap is a specialized tree-based data structure that satisfies the heap property. It is…
What is the Lowest Common Ancestor? In a tree, the lowest common ancestor (LCA) of…
A Binary Search Tree (BST) is a type of binary tree that satisfies the following…
In binary trees, the views and types refer to different perspectives and classifications of the…