Trie (Prefix Tree)

Introduction

Trie is a search tree, which is used to store/search strings in an efficient way. In a trie, any node can store non-repetitive multiple characters. Every node stores the’ link’ of the next character of the string. Every node also keeps track of the “end of the word”.

Algorithms

Insertion

• Every character of the input key is inserted as an individual Trie node. Note that the children are a reference to next-level trie nodes.
• The key character acts as an index to the array of children.
• If the input key is new or an extension of an existing key, we need to construct non-existing nodes of the key and mark the “end of the word” for the last node.
• If the input key is a prefix of an existing key in Trie, we simply mark the last node of the key as the end of the word.
• The key length determines Trie depth.

Searching

• The search can terminate due to the end of the string or lack of key in the trie.
• In the former case, if the isEndofWord field of the last node is true, then the key exists in the trie.
• In the second case, the search terminates without examining all the characters of the key, since the key is not present in the trie.

Implementation

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

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

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

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

Runtime