Implement a Trie Prefix Tree perform basic operations Python Program

 Implement a Trie (Prefix Tree): Implement a trie data structure and perform basic operations like insert, search, and startsWith Python Program?

A Trie (or Prefix Tree) is a tree-like data structure that is used to efficiently store and retrieve strings based on their prefixes. It is particularly useful for tasks like autocomplete, spell checking, and prefix matching.

Here’s a Python implementation of a Trie with basic operations:

1. Insert: Add a word to the Trie.
2. Search: Check if a word is in the Trie.
3. StartsWith: Check if there is any word in the Trie that starts with a given prefix.

Trie Node Class

Each node in the Trie contains:

• A dictionary of children nodes.
• A boolean flag to indicate if the node represents the end of a word.

Trie Class

The Trie class contains:

• The root node.
• Methods to insert words, search for words, and check if any words start with a given prefix.

Here's the Python implementation:

class TrieNode:

    def __init__(self):

        self.children = {}

        self.is_end_of_word = False

class Trie:

    def __init__(self):

        self.root = TrieNode()

    def insert(self, word):

        node = self.root

        for char in word:

            if char not in node.children:

                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_end_of_word = True

    def search(self, word):

        node = self.root

        for char in word:

            if char not in node.children:

                return False

            node = node.children[char]

        return node.is_end_of_word

    def startsWith(self, prefix):

        node = self.root

        for char in prefix:

            if char not in node.children:

                return False

            node = node.children[char]

        return True

# Example usage:

trie = Trie()

trie.insert("apple")

print(trie.search("apple"))   # Output: True

print(trie.search("app"))     # Output: False

print(trie.startsWith("app")) # Output: True

print(trie.startsWith("appl"))# Output: True

print(trie.search("appl"))    # Output: False

Explanation

1. TrieNode Class:

   • children: A dictionary where keys are characters, and values are TrieNode instances representing the next level of nodes.
   • is_end_of_word: A boolean flag indicating whether the node marks the end of a valid word.

2. Trie Class:

   • insert(word):
     • Traverse through the characters of the word.
     • Create new nodes as needed for each character.
     • Set the is_end_of_word flag to True for the last character of the word.
   • search(word):
     • Traverse through the characters of the word.
     • Check if each character exists in the Trie nodes.
     • After traversing all characters, check if the last node has the is_end_of_word flag set to True.
   • startsWith(prefix):
     • Traverse through the characters of the prefix.
     • Check if each character exists in the Trie nodes.
     • If you can traverse through all characters of the prefix, it means there is a word starting with that prefix.

Complexity

• Time Complexity: Each operation (insert, search, startsWith) runs in $O(m)$, where $m$ is the length of the word or prefix.
• Space Complexity: The space complexity is $O(n \cdot m)$, where $n$ is the number of words inserted, and $m$ is the maximum length of a word. This is due to the space required for storing nodes in the Trie.