Skip to content

Instantly share code, notes, and snippets.

@akshaynagpal
Last active October 11, 2020 23:02
Show Gist options
  • Save akshaynagpal/1905768c6571f01c16bb4bc57eb8e48d to your computer and use it in GitHub Desktop.
Save akshaynagpal/1905768c6571f01c16bb4bc57eb8e48d to your computer and use it in GitHub Desktop.
Trie implementation in Python 3 from scratch
class TrieNode:
def __init__(self):
self.children = {}
self.isEndOfWord = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insertWord(self, word):
currNode = self.root
while word:
if word[0] not in currNode.children:
currNode.children[word[0]] = TrieNode()
currNode = currNode.children[word[0]]
word = word[1:]
currNode.isEndOfWord = True
def search(self, word):
currNode = self.root
while word:
if word[0] not in currNode.children:
return False
else:
currNode = currNode.children[word[0]]
word = word[1:]
return currNode.isEndOfWord
trie = Trie()
trie.insertWord("hell")
trie.insertWord("hello")
trie.insertWord("bye")
trie.insertWord("")
assert(trie.search("") == True) # should return True
assert(trie.search("bye") == True) # should return True
assert(trie.search("hell") == True) # should return True
assert(trie.search("hello") == True) # should return True
assert(trie.search("by") == False) # should return False
@akshaynagpal
Copy link
Author

akshaynagpal commented Oct 11, 2020

It was fun trying to implement a simple trie class in python. Star it if it was useful for you, feels nice getting a star from an internet stranger :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment