Trie Data structure using Python

A Trie is a tree-like data structure that stores a dynamic set of strings. It is often used as an efficient way to search for patterns in a large text dataset, as well as for implementing spell checkers. Here is an example of how you could implement a Trie in Python:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

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

    def insert(self, word: str) -> None:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.is_word = True

    def search(self, word: str) -> bool:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return curr.is_word

    def starts_with(self, prefix: str) -> bool:
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True

This implementation includes three methods:

• insert(word: str): adds the given word to the Trie
• search(word: str): returns True if the word is in the Trie, False otherwise
• starts_with(prefix: str): returns True if there is any word in the Trie that starts with the given prefix, False otherwise

You can use the Trie like this:

trie = Trie()

trie.insert("Ankush")
trie.insert("Kunwar")

print(trie.search("Ankush"))  # True
print(trie.search("anks"))   # False
print(trie.search("world"))  # False

print(trie.starts_with("Ank"))  # True
print(trie.starts_with("Kun"))  # True
print(trie.starts_with("ha"))  # False

Thank you for reading !!!

If you enjoy this article and would like to Buy Me a Coffee, please click here.

you can connect with me on Linkedin.