Description
A trie, is a Tree like DS, which uses a dict for the children.
root =
Runtime
O(n)
Visualization
Pseudocode
Traverse the tree, if a node does not exist add it.
Code
trie = {}
def insert(word):
node = trie
for ch in word:
if ch not in node:
node[ch] = {}
node = node[ch]
def has_prefix(prefix):
node = trie
for ch in prefix:
if ch not in node:
return False
node = node[ch]
return True