Remarks

  • Trie(pronounce as try) or Prefix Tree is a N-way tree used to facilitate search of string valued keys.
  • The node path corresponds to the characters in the key.
  • We use a flag to indicate the end of key.
  • Trie can be implemented with Tree Nodes or as hashmap of hashmaps.
  • The basic operations like add, contains or prefix search startswith all take \(O(k)\) time where k = len(key)

Implementation

class TrieNode(defaultdict):
    def __init__(self):
        self.default_factory = TrieNode
        self.terminal = False

def add(root, word):
    node = root
    for c in word:
        node = node[c]
    node.terminal = True

def contains(root, word):
    node = root
    for i, c in enumerate(word):
        if c not in node: return False
        node = node[c]
    return node.terminal

def startswith(root, word):
    node = root
    for c in word:
        if c not in node: return False
        node = node[c]
    return True

root = TrieNode()

words = ["hello", "hell", "hehe", "what"]
for word in words: add(root, word)

queries = ["hello", "hel", "he", "w", "are"]
for query in queries: print(f"{query} in trie: {contains(root, query)}")

for query in queries: print(f"{query} is a prefix in trie: {startswith(root, query)}")

Sample Questions

Implementation

String Prefix / Suffix Search

File System

Application

Other uncategorized