Trie Data Structure | Insert and Search

Last Updated : 07 Jun, 2024

The Trie data structure is a tree-like data structure used for storing a dynamic set of strings. It is commonly used for efficient retrieval and storage of keys in a large dataset. The structure supports operations such as insertion, search, and deletion of keys, making it a valuable tool in fields like computer science and information retrieval. In this article we are going to explore insertion and search operation in Trie Data Structure.

Trie data structure

Trie data structure

Table of Content

Representation of of Trie Node
Insertion in Trie Data Structure
Searching in Trie Data Structure
Implementation of Insert and Search Operations in Trie
Complexity Analysis of Trie Data Structure

Representation of of Trie Node:

A Trie data structure consists of nodes connected by edges. Each node represents a character or a part of a string. The root node, the starting point of the Trie, represents an empty string. Each edge emanating from a node signifies a specific character. The path from the root to a node represents the prefix of a string stored in the Trie.

A simple structure to represent nodes of the English alphabet can be as follows.

C++

struct TrieNode {

    // pointer array for child nodes of each node
    TrieNode* childNode[26];

    // Used for indicating ending of string
    bool wordEnd;

    TrieNode()
    {
        // constructor
        // initialize the wordEnd variable with false
        // initialize every index of childNode array with
        // NULL
        wordEnd = false;
        for (int i = 0; i < 26; i++) {
            childNode[i] = NULL;
        }
    }
};

Java

public class TrieNode {
    
    // Array for child nodes of each node
    TrieNode[] childNode;
    
    // Used for indicating the end of a string
    boolean wordEnd;

    // Constructor
    public TrieNode() {
        // Initialize the wordEnd variable with false
        wordEnd = false;

        // Initialize every index of the childNode array with null
        childNode = new TrieNode[26];
        for (int i = 0; i < 26; i++) {
            childNode[i] = null;
        }
    }
}

Insertion in Trie Data Structure:

Let’s walk through the process of inserting the words into a Trie data structure. We have already cover the basics of Trie and its node structure.

Here’s a visual representation of inserting the words “and” and “ant” into a Trie data structure:

Insert Operation in Trie Data Structure

Inserting “and” in Trie data structure:

Start at the root node: The root node has no character associated with it and its wordEnd value is 0, indicating no complete word ends at this point.
First character “a”: Calculate the index using ‘a’ – ‘a’ = 0. Check if the childNode[0] is null. Since it is, create a new TrieNode with the character “a“, wordEnd set to 0, and an empty array of pointers. Move to this new node.
Second character “n”: Calculate the index using ‘n’ – ‘a’ = 13. Check if childNode[13] is null. It is, so create a new TrieNode with the character “n“, wordEnd set to 0, and an empty array of pointers. Move to this new node.
Third character “d”: Calculate the index using ‘d’ – ‘a’ = 3. Check if childNode[3] is null. It is, so create a new TrieNode with the character “d“, wordEnd set to 1 (indicating the word “and” ends here).
Inserting “ant” in Trie data structure:

Start at the root node: Root node doesn’t contain any data but it keep track of every first character of every string that has been inserted.
First character “a”: Calculate the index using ‘a’ – ‘a’ = 0. Check if the childNode[0] is null. We already have the “a” node created from the previous insertion. so move to the existing “a” node.
First character “n”: Calculate the index using ‘n’ – ‘a’ = 13. Check if childNode[13] is null. It’s not, so move to the existing “n” node.
Second character “t”: Calculate the index using ‘t’ – ‘a’ = 19. Check if childNode[19] is null. It is, so create a new TrieNode with the character “t“, wordEnd set to 1 (indicating the word “ant” ends here).

Below is the implementation of insertion of strings in Trie data structure:

C++

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {

    // pointer array for child nodes of each node
    TrieNode* childNode[26];

    // Used for indicating ending of string
    bool wordEnd;

    TrieNode()
    {
        // constructor
        // initialize the wordEnd variable with false
        // initialize every index of childNode array with
        // NULL
        wordEnd = false;
        for (int i = 0; i < 26; i++) {
            childNode[i] = NULL;
        }
    }
};

void insert_key(TrieNode* root, string& key)
{
    // Initialize the currentNode pointer
    // with the root node
    TrieNode* currentNode = root;

    // Iterate across the length of the string
    for (auto c : key) {

        // Check if the node exist for the current
        // character in the Trie.
        if (currentNode->childNode[c - 'a'] == NULL) {

            // If node for current character does not exist
            // then make a new node
            TrieNode* newNode = new TrieNode();

            // Keep the reference for the newly created
            // node.
            currentNode->childNode[c - 'a'] = newNode;
        }

        // Now, move the current node pointer to the newly
        // created node.
        currentNode = currentNode->childNode[c - 'a'];
    }

    // Increment the wordEndCount for the last currentNode
    // pointer this implies that there is a string ending at
    // currentNode.
    currentNode->wordEnd = 1;
}

Time Complexity: O(number of words * maxLengthOfWord)
Auxiliary Space: O(number of words * maxLengthOfWord)

Searching in Trie Data Structure:

Searching for a key in Trie data structure is similar to its insert operation. However, It only compares the characters and moves down. The search can terminate due to the end of a string or lack of key in the trie.

Steps by step approach for searching in Trie Data structure:

Start at the root node. This is the starting point for all searches within the Trie.
Traverse the Trie based on the characters of the word you are searching for. For each character, follow the corresponding branch in the Trie. If the branch doesn’t exist, the word is not present in the Trie.
If you reach the end of the word and the wordEnd flag is set to 1, the word has been found.
If you reach the end of the word and the wordEnd flag is 0, the word is not present in the Trie, even though it shares a prefix with an existing word.

Here’s a visual representation of searching word “dad” in Trie data structure:

Let’s assume that we have successfully inserted the words “and“, “ant“, and “dad” into our Trie, and we have to search for specific words within the Trie data structure. Let’s try searching for the word “dad“:

Search Operation in Trie Data Structure

We start at the root node.
We follow the branch corresponding to the character ‘d’.
We follow the branch corresponding to the character a’.
We follow the branch corresponding to the character ‘d’.
We reach the end of the word and wordEnd flag is 1. This means that “dad” is present in the Trie.

Below is the implementation of searching strings in Trie Data Structure:

C++

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {

    // pointer array for child nodes of each node
    TrieNode* childNode[26];

    // Used for indicating ending of string
    bool wordEnd;

    TrieNode()
    {
        // constructor
        // initialize the wordEnd variable with false
        // initialize every index of childNode array with
        // NULL
        wordEnd = false;
        for (int i = 0; i < 26; i++) {
            childNode[i] = NULL;
        }
    }
};

bool search_key(TrieNode* root, string& key)
{
    // Initialize the currentNode pointer
    // with the root node
    TrieNode* currentNode = root;

    // Iterate across the length of the string
    for (auto c : key) {

        // Check if the node exist for the current
        // character in the Trie.
        if (currentNode->childNode[c - 'a'] == NULL) {

            // Given word does not exist in Trie
            return false;
        }

        // Move the currentNode pointer to the already
        // existing node for current character.
        currentNode = currentNode->childNode[c - 'a'];
    }

    return (currentNode->wordEnd == true);
}

Time Complexity: O(number of words * maxLengthOfWord)
Auxiliary Space: O(number of words * maxLengthOfWord)

Implementation of Insert and Search Operations in Trie Data Structure:

Steps-by-step approach:

Create a root node with the help of TrieNode() constructor.
Store a collection of strings that have to be inserted in the trie in a vector of strings say, arr.
Inserting all strings in Trie with the help of the insert_key() function,
Search strings with the help of search_key() function.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {

    // pointer array for child nodes of each node
    TrieNode* childNode[26];

    // Used for indicating ending of string
    bool wordEnd;

    TrieNode()
    {
        // constructor
        // initialize the wordEnd variable with false
        // initialize every index of childNode array with
        // NULL
        wordEnd = false;
        for (int i = 0; i < 26; i++) {
            childNode[i] = NULL;
        }
    }
};

void insert_key(TrieNode* root, string& key)
{
    // Initialize the currentNode pointer
    // with the root node
    TrieNode* currentNode = root;

    // Iterate across the length of the string
    for (auto c : key) {

        // Check if the node exist for the current
        // character in the Trie.
        if (currentNode->childNode[c - 'a'] == NULL) {

            // If node for current character does not exist
            // then make a new node
            TrieNode* newNode = new TrieNode();

            // Keep the reference for the newly created
            // node.
            currentNode->childNode[c - 'a'] = newNode;
        }

        // Now, move the current node pointer to the newly
        // created node.
        currentNode = currentNode->childNode[c - 'a'];
    }

    // Increment the wordEndCount for the last currentNode
    // pointer this implies that there is a string ending at
    // currentNode.
    currentNode->wordEnd = 1;
}

bool search_key(TrieNode* root, string& key)
{
    // Initialize the currentNode pointer
    // with the root node
    TrieNode* currentNode = root;

    // Iterate across the length of the string
    for (auto c : key) {

        // Check if the node exist for the current
        // character in the Trie.
        if (currentNode->childNode[c - 'a'] == NULL) {

            // Given word does not exist in Trie
            return false;
        }

        // Move the currentNode pointer to the already
        // existing node for current character.
        currentNode = currentNode->childNode[c - 'a'];
    }

    return (currentNode->wordEnd == true);
}

// Driver code
int main()
{
    // Make a root node for the Trie
    TrieNode* root = new TrieNode();

    // Stores the strings that we want to insert in the
    // Trie
    vector<string> inputStrings
        = { "and", "ant", "do", "geek", "dad", "ball" };

    // number of insert operations in the Trie
    int n = inputStrings.size();

    for (int i = 0; i < n; i++) {
        insert_key(root, inputStrings[i]);
    }

    // Stores the strings that we want to search in the Trie
    vector<string> searchQueryStrings
        = { "do", "geek", "bat" };

    // number of search operations in the Trie
    int searchQueries = searchQueryStrings.size();

    for (int i = 0; i < searchQueries; i++) {
        cout << "Query String: " << searchQueryStrings[i]
             << "\n";
        if (search_key(root, searchQueryStrings[i])) {
            // the queryString is present in the Trie
            cout << "The query string is present in the "
                    "Trie\n";
        }
        else {
            // the queryString is not present in the Trie
            cout << "The query string is not present in "
                    "the Trie\n";
        }
    }

    return 0;
}

Java

class TrieNode {
    TrieNode[] childNode;
    boolean wordEnd;

    TrieNode()
    {
        childNode = new TrieNode[26];
        wordEnd = false;
    }
}

class Trie {
    TrieNode root;

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

    // Function to insert a key into the Trie
    void insert(String key)
    {
        TrieNode currentNode = root;
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (currentNode.childNode[index] == null) {
                currentNode.childNode[index]
                    = new TrieNode();
            }
            currentNode = currentNode.childNode[index];
        }
        currentNode.wordEnd = true;
    }

    // Function to search for a key in the Trie
    boolean search(String key)
    {
        TrieNode currentNode = root;
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (currentNode.childNode[index] == null) {
                return false;
            }
            currentNode = currentNode.childNode[index];
        }
        return currentNode.wordEnd;
    }
}

public class Main {
    public static void main(String[] args)
    {
        Trie trie = new Trie();
        String[] inputStrings
            = { "and", "ant", "do", "geek", "dad", "ball" };
        // Insert each string into the Trie
        for (String str : inputStrings) {
            trie.insert(str);
        }
        String[] searchQueryStrings
            = { "do", "geek", "bat" };
        // Search for each string and print whether it is
        // found in the Trie
        for (String query : searchQueryStrings) {
            System.out.println("Query String: " + query);
            if (trie.search(query)) {
                System.out.println(
                    "The query string is present in the Trie");
            }
            else {
                System.out.println(
                    "The query string is not present in the Trie");
            }
        }
    }
}

Python

class TrieNode:
    def __init__(self):
        self.childNode = [None] * 26
        self.wordEnd = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    # Function to insert a key into the Trie
    def insert(self, key):
        currentNode = self.root
        for char in key:
            index = ord(char) - ord('a')
            if not currentNode.childNode[index]:
                currentNode.childNode[index] = TrieNode()
            currentNode = currentNode.childNode[index]
        currentNode.wordEnd = True

    # Function to search for a key in the Trie
    def search(self, key):
        currentNode = self.root
        for char in key:
            index = ord(char) - ord('a')
            if not currentNode.childNode[index]:
                return False
            currentNode = currentNode.childNode[index]
        return currentNode.wordEnd


if __name__ == "__main__":
    trie = Trie()
    inputStrings = ["and", "ant", "do", "geek", "dad", "ball"]

    # Insert each string into the Trie
    for word in inputStrings:
        trie.insert(word)

    searchQueryStrings = ["do", "geek", "bat"]
    # Search for each string and print whether it is found in the Trie
    for query in searchQueryStrings:
        print("Query String:", query)
        if trie.search(query):
            print("The query string is present in the Trie")
        else:
            print("The query string is not present in the Trie")

JavaScript

class TrieNode {
    constructor() {
        // Initialize the childNode array with 26 nulls
        this.childNode = Array(26).fill(null);
        // Initialize wordEnd to the false indicating that no word ends here yet
        this.wordEnd = false;
    }
}
class Trie {
    constructor() {
        // Initialize the root node of the Trie
        this.root = new TrieNode();
    }
    // Function to insert a key into the Trie
    insert(key) {
        // Start from the root node
        let currentNode = this.root;
        for (let i = 0; i < key.length; i++) {
            const index = key.charCodeAt(i) - 'a'.charCodeAt(0);
            if (currentNode.childNode[index] === null) {
                currentNode.childNode[index] = new TrieNode();
            }
            // Move to the next node in the Trie
            currentNode = currentNode.childNode[index];
        }
        // Mark the end of the word
        currentNode.wordEnd = true;
    }
    // Function to search for a key in the Trie
    search(key) {
        // Start from the root node
        let currentNode = this.root;
        // Iterate through each character in the key
        for (let i = 0; i < key.length; i++) {
            const index = key.charCodeAt(i) - 'a'.charCodeAt(0);
            if (currentNode.childNode[index] === null) {
                return false;
            }
            // Move to the next node in the Trie
            currentNode = currentNode.childNode[index];
        }
        // Return true if the end of the word is marked otherwise false
        return currentNode.wordEnd;
    }
}
// Driver code
const trie = new Trie();
const inputStrings = ["and", "ant", "do", "geek", "dad", "ball"];
// Insert each string into the Trie
inputStrings.forEach((str) => trie.insert(str));
const searchQueryStrings = ["do", "geek", "bat"];
// Search for each string and print whether it is found in the Trie
searchQueryStrings.forEach((query) => {
    console.log(`Query String: ${query}`);
    if (trie.search(query)) {
        console.log("The query string is present in the Trie");
    } else {
        console.log("The query string is not present in the Trie");
    }
});

Output

Query String: do
The query string is present in the Trie
Query String: geek
The query string is present in the Trie
Query String: bat
The query string is not present in the Trie

Complexity Analysis of Trie Data Structure:

Operation	Time Complexity	Auxiliary Space
Insertion	O(n)	O(n*m)
Searching	O(n)	O(1)

Related Articles:

Practice Problems:

V

Venki

Improve

Trie Data Structure using smart pointer and OOP in C++

Similar Reads

Design a data structure that supports insert, delete, search and getRandom in constant time

Design a data structure that supports the following operations in O(1) time. insert(x): Inserts an item x to the data structure if not already present.remove(x): Removes item x from the data structure if present. search(x): Searches an item x in the data structure.getRandom(): Returns a random element from the current set of elements We can use has

Trie Data Structure using smart pointer and OOP in C++

We will implement trie using smart pointers in C++ and OOP. Here, We have already discussed the implementation of trie data using recursionIn our implementation node of a trie look like : C/C++ Code class TrieNode{ public: // Use of shared_ptr for storing Children // Pointers of TrieNode shared_ptr children[ALPHABET_SIZE]; // Tracks whether If this

Advantages of Trie Data Structure

Introduction: Trie (also known as prefix tree) is a tree-based data structure that is used to store an associative array where the keys are sequences (usually strings). Some advantages of using a trie data structure include:Fast search: Tries support fast search operations, as we can search for a key by traversing down the tree from the root, and t

Search in a trie Recursively

Trie is an efficient information retrieval data structure. Using Trie, search complexities can be brought to an optimal limit (key length).The task is to search a string in a Trie using recursion.Examples : root / \ t a | | h n | | \ e s y / | | i r w | | | r e e | r Input : str = "anywhere" Output : not found Input : str = "answer" Output : found

Static Data Structure vs Dynamic Data Structure

Data structure is a way of storing and organizing data efficiently such that the required operations on them can be performed be efficient with respect to time as well as memory. Simply, Data Structure are used to reduce complexity (mostly the time complexity) of the code. Data structures can be two types : 1. Static Data Structure 2. Dynamic Data

Overview of Graph, Trie, Segment Tree and Suffix Tree Data Structures

Introduction:Graph: A graph is a collection of vertices (nodes) and edges that represent relationships between the vertices. Graphs are used to model and analyze networks, such as social networks or transportation networks.Trie: A trie, also known as a prefix tree, is a tree-like data structure that stores a collection of strings. It is used for ef

Design a data structure that supports insert, delete, getRandom in O(1) with duplicates

Design a Data Structure that can support the following operations in O(1) Time Complexity. insert(x): Inserts x in the data structure. Returns True if x was not present and False if it was already present.remove(x): Removes x from the data structure, if present.getRandom(): Returns any value present in the stream randomly. The probability of each e

Add and Search Word - Data Structure Design

Design a data structure GFGDictionary that enables to support the feature of adding new words and searching for words. The GFGDictionary class should have the following implementation: GFGDictionary(): constructor to initialize the objectvoid insertWord(word): function to insert word into the data structure.bool findWord(word): function to return t

2-3 Trees | (Search, Insert and Deletion)

In binary search trees we have seen the average-case time for operations like search/insert/delete is O(log N) and the worst-case time is O(N) where N is the number of nodes in the tree. Like other Trees include AVL trees, Red Black Tree, B tree, 2-3 Tree is also a height balanced tree. The time complexity of search/insert/delete is O(log N) . A 2-

Implementation of Search, Insert and Delete in Treap

We strongly recommend to refer set 1 as a prerequisite of this post.Treap (A Randomized Binary Search Tree)In this post, implementations of search, insert and delete are discussed.Search: Same as standard BST search. Priority is not considered for search. C/C++ Code // C function to search a given key in a given BST TreapNode* search(TreapNode* roo

Article Tags :

Practice Tags :