Trie Implementation and Operations

Intuition

A Trie is a specialized tree-like data structure that organizes and stores words in an efficient manner. Each node in a Trie represents a single character of a word, allowing for efficient addition, retrieval, and deletion of words. In simpler terms, a Trie is an advanced information retrieval data structure. It outperforms more conventional data structures like Hashmaps and Trees in terms of the time complexity for various operations, making it particularly useful for tasks involving large sets of strings or words. The Trie data structure is designed to store and quickly retrieve a collection of strings. It arranges strings so that shared prefixes are stored once, which makes it very efficient for operations like searching for words with a specific prefix. This ability to quickly find all strings that start with a given prefix makes Tries particularly useful for applications like autocomplete and predictive text. Trie Node Structure

A Trie node is a fundamental element used to build a Trie. Each node consists of the following parts:

Child Node Links: A Trie node has an array of pointers, often referred to as "links" or "children pointers," for every letter of the lowercase alphabet. These pointers create connections to child nodes that represent each letter of the alphabet. For example, the link at index 0 corresponds to the child node for the letter 'a', the link at index 1 corresponds to 'b', and so on.
End-of-Word Flag: Each Trie node includes a boolean flag that signifies whether the node marks the end of a word. This flag is crucial for differentiating between prefixes and full words stored in the Trie.

Each node in the Trie supports several key operations:

Contains Key: This operation checks if a specific letter (or key) exists as a child node of the current Trie node. It returns true if the letter is present, indicating a valid path in the Trie.
Get Child Node: Given a letter, this operation retrieves the corresponding child node from the current Trie node. If the letter is present, it returns a pointer to the child node; otherwise, it returns null, indicating the letter is absent.
Put Child Node: This operation creates a link between the current Trie node and a child node representing a specific letter. It sets the link at the corresponding index to point to the given child node.
Set End Flag: This operation marks the current Trie node as the end of a word. This flag is essential for determining if a string stored in the Trie ends at this node, indicating a complete word.
Is End of Word: This operation checks if the current Trie node marks the end of a word by examining the end flag. It returns true if the node signifies the end of a word; otherwise, it returns false.

Approach

To insert a Node in The Trie

Begin at the root node.
For each character in the word:
- Check if the current node has a child node for the character.
- If the child node doesn't exist, create a new node and link it to the current node.
- Move to the child node that corresponds to the character.
After inserting all characters, mark the end of the word by setting the end flag of the last node to true.

To search for a word in Trie

Begin at the root node.
For each character in the word:
- Verify if the current node has a child node for the character.
- If not, the word is not present in the Trie.
- Move to the child node corresponding to the character.
After processing all characters, check if the end flag of the last node is set to true. If it is, the word is found; if not, the word is not in the Trie.

Check if Trie contains Prefix

Begin at the root node.
For each character in the prefix:
- Check if the current node has a child node for the character.
- If it doesn't, there is no word with the given prefix.
- Move to the child node that corresponds to the character.
If all characters of the prefix are found, return true to indicate that there are words with the given prefix.

Dry Run

For more details, watch the video.

Solution

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

// Node Structure for Trie
struct Node {
    /*Array to store links to child nodes,
    each index represents a letter*/
    Node* links[26];
   /* Flag indicating if 
   the node marks the end 
   of a word*/
    bool flag = false;

    /*Check if the node contains
    a specific key (letter)*/
    bool containsKey(char ch) {
        return links[ch - 'a'] != NULL;
    }

   /* Insert a new node with a specific
    key (letter) into the Trie*/
    void put(char ch, Node* node) {
        links[ch - 'a'] = node;
    }

    /*Get the node with a specific
    key (letter) from the Trie*/
    Node* get(char ch) {
        return links[ch - 'a'];
    }

    /*Set the current node
    as the end of a word*/
    void setEnd() {
        flag = true;
    }

    /*Check if the 
    current node marks 
    the end of a word*/
    bool isEnd() {
        return flag;
    }
};

// Trie class
class Trie {
private:
    Node* root;

public:
   /* Constructor to 
   initialize the
   Trie with an 
   empty root node*/
    Trie() {
        root = new Node();
    }

   /* Inserts a word into the Trie
    Time Complexity O(len), where len
    is the length of the word*/
    void insert(string word) {
        Node* node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node->containsKey(word[i])) {
               /* Create a new node for
                the letter if not present*/
                node->put(word[i], new Node());
            }
            // Move to the next node
            node = node->get(word[i]);
        }
        // Mark the end of the word
        node->setEnd();
    }

    /*Returns if the word
    is in the trie*/
    bool search(string word) {
        Node* node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node->containsKey(word[i])) {
                /*If a letter is 
                not found,the word 
                is not in the Trie*/
                return false;
            }
            // Move to the next node
            node = node->get(word[i]);
        }
        /*Check if the last node
        marks the end of a word*/
        return node->isEnd();
    }

   /* Returns if there is any word in the
    trie that starts with the given prefix*/
    bool startsWith(string prefix) {
        Node* node = root;
        for (int i = 0; i < prefix.length(); i++) {
            if (!node->containsKey(prefix[i])) {
                /*If a letter is not 
                found, there is
                no word with the 
                given prefix*/
                return false;
            }
            // Move to the next node
            node = node->get(prefix[i]);
        }
        // Prefix Found
        return true;
    }
};

int main() {
    // Create a Trie object
    Trie* trie = new Trie();

    // Define input operations and arguments
    vector<string> operations = {"Trie", "insert", "search", "search", "startsWith", "insert", "search"};
    vector<vector<string>> arguments = { {}, {"apple"}, {"apple"}, {"app"}, {"app"}, {"app"}, {"app"} };

    // Execute operations
    vector<string> output;
    for (int i = 0; i < operations.size(); i++) {
        if (operations[i] == "Trie") {
            output.push_back("null");
        } else if (operations[i] == "insert") {
            trie->insert(arguments[i][0]);
            output.push_back("null");
        } else if (operations[i] == "search") {
            bool result = trie->search(arguments[i][0]);
            output.push_back(result ? "true" : "false");
        } else if (operations[i] == "startsWith") {
            bool result = trie->startsWith(arguments[i][0]);
            output.push_back(result ? "true" : "false");
        }
    }

    // Print output
    for (string res : output) {
        cout << res << endl;
    }

    // Clean up
    delete trie;

    return 0;
}
import java.util.*;

class Node {
    /* Array to store links to child nodes,
    each index represents a letter */
    private Node[] links;
    /* Flag indicating if the node
    marks the end of a word */
    private boolean flag;

    // Constructor
    public Node() {
        links = new Node[26];
        flag = false;
    }

    /* Check if the node contains
    a specific key (letter) */
    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    /* Insert a new node with a specific
    key (letter) into the Trie */
    public void put(char ch, Node node) {
        links[ch - 'a'] = node;
    }

    /* Get the node with a specific
    key (letter) from the Trie */
    public Node get(char ch) {
        return links[ch - 'a'];
    }

    /* Set the current node
    as the end of a word */
    public void setEnd() {
        flag = true;
    }

    /* Check if the current node
    marks the end of a word */
    public boolean isEnd() {
        return flag;
    }
}

// Trie class
class Trie {
    private Node root;

    /* Constructor to initialize the
    Trie with an empty root node */
    public Trie() {
        root = new Node();
    }

    /* Inserts a word into the Trie
    Time Complexity O(len), where len
    is the length of the word */
    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node.containsKey(word.charAt(i))) {
                /* Create a new node for
                the letter if not present */
                node.put(word.charAt(i), new Node());
            }
            // Move to the next node
            node = node.get(word.charAt(i));
        }
        // Mark the end of the word
        node.setEnd();
    }

    /* Returns if the word
    is in the trie */
    public boolean search(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node.containsKey(word.charAt(i))) {
                /* If a letter is not found,
                the word is not in the Trie */
                return false;
            }
            // Move to the next node
            node = node.get(word.charAt(i));
        }
        /* Check if the last node
        marks the end of a word */
        return node.isEnd();
    }

    /* Returns if there is any word in the
    trie that starts with the given prefix */
    public boolean startsWith(String prefix) {
        Node node = root;
        for (int i = 0; i < prefix.length(); i++) {
            if (!node.containsKey(prefix.charAt(i))) {
                /* If a letter is not found,
                there is no word with the
                given prefix */
                return false;
            }
            // Move to the next node
            node = node.get(prefix.charAt(i));
        }
        // The prefix is found in the Trie
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        // Create a Trie object
        Trie trie = new Trie();

        // Define input operations and arguments
        List<String> operations = Arrays.asList("Trie", "insert", "search", "search", "startsWith", "insert", "search");
        List<List<String>> arguments = Arrays.asList(
            Collections.emptyList(),
            Collections.singletonList("apple"),
            Collections.singletonList("apple"),
            Collections.singletonList("app"),
            Collections.singletonList("app"),
            Collections.singletonList("app"),
            Collections.singletonList("app")
        );

        // Execute operations
        List<String> output = new ArrayList<>();
        for (int i = 0; i < operations.size(); i++) {
            if (operations.get(i).equals("Trie")) {
                output.add("null");
            } else if (operations.get(i).equals("insert")) {
                trie.insert(arguments.get(i).get(0));
                output.add("null");
            } else if (operations.get(i).equals("search")) {
                boolean result = trie.search(arguments.get(i).get(0));
                output.add(result ? "true" : "false");
            } else if (operations.get(i).equals("startsWith")) {
                boolean result = trie.startsWith(arguments.get(i).get(0));
                output.add(result ? "true" : "false");
            }
        }

        // Print output
        for (String res : output) {
            System.out.println(res);
        }
    }
}
class Node:
    def __init__(self):
        # Array to store links to child nodes,
        # each index represents a letter
        self.links = [None] * 26
        # Flag indicating if the node
        # marks the end of a word
        self.flag = False

    # Check if the node contains
    # a specific key (letter)
    def containsKey(self, ch):
        return self.links[ord(ch) - ord('a')] is not None

    # Insert a new node with a specific
    # key (letter) into the Trie
    def put(self, ch, node):
        self.links[ord(ch) - ord('a')] = node

    # Get the node with a specific
    # key (letter) from the Trie
    def get(self, ch):
        return self.links[ord(ch) - ord('a')]

    # Set the current node
    # as the end of a word
    def setEnd(self):
        self.flag = True

    # Check if the current node
    # marks the end of a word
    def isEnd(self):
        return self.flag

class Trie:
    def __init__(self):
        # Constructor to initialize the
        # Trie with an empty root node
        self.root = Node()

    # Inserts a word into the Trie
    # Time Complexity O(len), where len
    # is the length of the word
    def insert(self, word):
        node = self.root
        for ch in word:
            if not node.containsKey(ch):
                # Create a new node for
                # the letter if not present
                node.put(ch, Node())
            # Move to the next node
            node = node.get(ch)
        # Mark the end of the word
        node.setEnd()

    # Returns if the word
    # is in the trie
    def search(self, word):
        node = self.root
        for ch in word:
            if not node.containsKey(ch):
                # If a letter is not found,
                # the word is not in the Trie
                return False
            # Move to the next node
            node = node.get(ch)
        # Check if the last node
        # marks the end of a word
        return node.isEnd()

    # Returns if there is any word in the
    # trie that starts with the given prefix
    def startsWith(self, prefix):
        node = self.root
        for ch in prefix:
            if not node.containsKey(ch):
                # If a letter is not found,
                # there is no word with the
                # given prefix
                return False
            # Move to the next node
            node = node.get(ch)
        # The prefix is found in the Trie
        return True

if __name__ == "__main__":
    # Create a Trie object
    trie = Trie()

    # Define input operations and arguments
    operations = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
    arguments = [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

    # Execute operations
    output = []
    for i in range(len(operations)):
        if operations[i] == "Trie":
            output.append("null")
        elif operations[i] == "insert":
            trie.insert(arguments[i][0])
            output.append("null")
        elif operations[i] == "search":
            result = trie.search(arguments[i][0])
            output.append("true" if result else "false")
        elif operations[i] == "startsWith":
            result = trie.startsWith(arguments[i][0])
            output.append("true" if result else "false")

    # Print output
    for res in output:
        print(res)
class Node {
    constructor() {
        /* Array to store links to child nodes,
        each index represents a letter */
        this.links = new Array(26).fill(null);
        /* Flag indicating if the node
        marks the end of a word */
        this.flag = false;
    }

    /* Check if the node contains
    a specific key (letter) */
    containsKey(ch) {
        return this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)] !== null;
    }

    /* Insert a new node with a specific
    key (letter) into the Trie */
    put(ch, node) {
        this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)] = node;
    }

    /* Get the node with a specific
    key (letter) from the Trie */
    get(ch) {
        return this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)];
    }

    /* Set the current node
    as the end of a word */
    setEnd() {
        this.flag = true;
    }

    /* Check if the current node
    marks the end of a word */
    isEnd() {
        return this.flag;
    }
}

// Trie class
class Trie {
    constructor() {
        /* Constructor to initialize the
        Trie with an empty root node */
        this.root = new Node();
    }

    /* Inserts a word into the Trie
    Time Complexity O(len), where len
    is the length of the word */
    insert(word) {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            if (!node.containsKey(word[i])) {
                /* Create a new node for
                the letter if not present */
                node.put(word[i], new Node());
            }
            // Move to the next node
            node = node.get(word[i]);
        }
        // Mark the end of the word
        node.setEnd();
    }

    /* Returns if the word
    is in the trie */
    search(word) {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            if (!node.containsKey(word[i])) {
                /* If a letter is not found,
                the word is not in the Trie */
                return false;
            }
            // Move to the next node
            node = node.get(word[i]);
        }
        /* Check if the last node
        marks the end of a word */
        return node.isEnd();
    }

    /* Returns if there is any word in the
    trie that starts with the given prefix */
    startsWith(prefix) {
        let node = this.root;
        for (let i = 0; i < prefix.length; i++) {
            if (!node.containsKey(prefix[i])) {
                /* If a letter is not found,
                there is no word with the
                given prefix */
                return false;
            }
            // Move to the next node
            node = node.get(prefix[i]);
        }
        // The prefix is found in the Trie
        return true;
    }
}

function main() {
    // Create a Trie object
    let trie = new Trie();

    // Define input operations and arguments
    let operations = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"];
    let arguments = [ [], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"] ];

    // Execute operations
    let output = [];
    for (let i = 0; i < operations.length; i++) {
        if (operations[i] === "Trie") {
            output.push("null");
        } else if (operations[i] === "insert") {
            trie.insert(arguments[i][0]);
            output.push("null");
        } else if (operations[i] === "search") {
            let result = trie.search(arguments[i][0]);
            output.push(result ? "true" : "false");
        } else if (operations[i] === "startsWith") {
            let result = trie.startsWith(arguments[i][0]);
            output.push(result ? "true" : "false");
        }
    }

    // Print output
    output.forEach(res => console.log(res));
}

main();

Complexity Analysis

Time Complexity:

Insertion: O(N), where N is the length of the word being inserted. This is because we need to go through each letter of the word to either find its corresponding node or create a new node as needed.
Search: O(N), where N is the length of the word being searched for. During a Trie search, we traverse each letter of the word starting from the root, checking if the current node has a child node at the position of the next letter. This continues until we either reach the end of the word or find a missing letter node.
Prefix Search: O(N), where N is the length of the prefix being searched for. Just like in word search, we go through each letter of the prefix to find its corresponding node.

Space Complexity: O(N) where N is the total number of characters across all unique words inserted into the Trie. For each character in a word, a new node might need to be created, resulting in space usage that is proportional to the total number of characters.

Problem List

Trie Implementation and Operations

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

To insert a Node in The Trie

To search for a word in Trie

Check if Trie contains Prefix

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code