Phone: +91 80884989467 Email: [email protected]
Follow us

Implementation of Trie (Prefix Tree)

IT & Software

What is Trie?

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Trie Data Structure

APIs of Trie:
  1. Trie() Initializes the trie object.
  2. void insert(String word) Inserts the string word into the trie.
  3. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  4. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Here is the code for Trie Data structure written in Python

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.EOW = None  # end of word


class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = Node()

    def _char_to_index(self, ch):
        # private helper function
        # Converts key current character into index
        # use only 'a' through 'z' and lower case
        return ord(ch) - ord('a')

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        root = self.root
        for level in range(len(word)):
            index = self._char_to_index(word[level])
            if not root.children[index]:
                root.children[index] = Node()
            root = root.children[index]
        root.EOW = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        root = self.root
        length = len(word)
        for level in range(length):
            index = self._char_to_index(word[level])
            if not root.children[index]:
                return False
            root = root.children[index]

        return root is not None and root.EOW

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        root = self.root
        length = len(prefix)
        for level in range(length):
            index = self._char_to_index(prefix[level])
            if not root.children[index]:
                return False
            root = root.children[index]
        return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# word = 'ajay'
# obj.insert(word)
# param_2 = obj.search('deed')
# print(param_2)
# param_3 = obj.startsWith('aj')
Time Complexity:

Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string), compared to an imperfect hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.

Reference: