# Implement a Prefix Tree (Trie)

Apr 1, 2021 ## Description

Implement a trie (prefix tree) with `insert`, `search`, and `startsWith` methods. Tries are used in many applications such as spell checking, autocompletion, and ip routing.

`insert(word)` Inserts the string word into the trie.

`search(word)` Returns `True` if the string word is in the trie (i.e., was inserted before), and `False` otherwise.

`startsWith(prefix)` Returns `True` if there is a previously inserted string word that has the prefix `prefix`, and `False` otherwise.

Part 2 of this problem (not shown on LeetCode) is to implement an `autoComplete` method.

## Solution 1: Using Node Class and Storing Entire Word at Leaf

This solution uses a `Node` class which makes things easier to keep track of. Storing the entire word in the end of word seperator makes the implementation less tricky. However this unfortunetly causes the space complexity to be `O(n)` where `n` is the number of words.

``````class Node:

def __init__(self, letter):
self.letter = letter
self.children = {}
self.end = False

class Trie:

def __init__(self):
self.root = Node('root')

def insert(self, word):
node = self.root
for letter in word:
if letter not in node.children:
node.children[letter] = Node(letter)
node = node.children[letter]
node.end = word

def search(self, word):
node = self.root
for letter in word:
if letter in node.children:
node = node.children[letter]
else:
return False
if node.end:
return True
else:
return False

def startsWith(self, prefix):
node = self.root
for letter in prefix:
if letter in node.children:
node = node.children[letter]
else:
return False
return True

def autocomplete(self, word):
node = self.root
for letter in word:
if letter in node.children:
node = node.children[letter]
else:
return []
words = []
autocomplete_helper(node, words)
return words

def autocomplete_helper(node, words):
if node.end:
words.append(node.end)
return
for child in node.children:
autocomplete_helper(node, words)
``````

## Solution 2: Using Just Dictionary and End of Word Marker \$

Since this only stores the letters, and not the entire word, the space complexity is much less.

``````class Trie:

def __init__(self):
self.root = {}

def insert(self, word):
node = self.root
for letter in word:
if letter not in node:
node[letter] = {}
node = node[letter]
node['\$'] = {} # End of word

def search(self, word):
node = self.root
for letter in word:
if letter in node:
node = node[letter]
else:
return False
if '\$' in node:
return True
else:
return False

def startsWith(self, prefix):
node = self.root
for letter in prefix:
if letter in node:
node = node[letter]
else:
return False
return True

def autoComplete(self, prefix):
node = self.root
for letter in prefix:
if letter in node:
node = node[letter]
else:
return []
words = []
autocomplete_helper(prefix, words, node)
return words

def autocomplete_helper(parent, words, node):
if '\$' in node:
words.append(parent)
for letter in node:
print_tree(parent + letter, words, node[letter])
``````

# Test Code and Benchmarking

``````trie = Trie()
trie.insert('cat')
trie.insert('can')
trie.insert('and')
trie.insert('ant')
trie.insert('antenna')

print(trie.autocomplete('an'))
``````

Using a list of 8000 most frequently searched words, here are some benchmarks.

``````77848 Bytes using python list
1184  Bytes using above trie

Input: p
Trie:  4.71 ms
List:  4.28 ms

Input: cat
Trie: 0.25 ms
List: 5.19 ms

Input: python
Trie:  0.05 ms
List:  7.81 ms
``````