Implement Trie Prefix Tree

Problem Summary

• Implement a Trie data structure with insert(), search(), startsWith()

Key Observations

• startsWith() cannot be $O(n)$

Approach Taken

• Create a TrieNode class that stores
  • children for key, value pair of other TrieNodes
  • isEndOfWord boolean to indicate whether a letter is the end of a word

Main Concepts Used

• Trie
• Hash Map

Time & Space Complexity

• Time: $O()$ → Reason:
• Space: $O()$ → Reason:

Code

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

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

    def insert(self, word: str) -> None:
        currentRoot = self.root

        for letter in word:
            if letter not in currentRoot.children:
                currentRoot.children[letter] = TrieNode()
            currentRoot = currentRoot.children[letter]

        currentRoot.isEnd = True

    def search(self, word: str) -> bool:
        currentRoot = self.root

        for letter in word:
            if letter not in currentRoot.children:
                return False
            currentRoot = currentRoot.children[letter]

        return currentRoot.isEnd

    def startsWith(self, prefix: str) -> bool:
        currentRoot = self.root

        for letter in prefix:
            if letter not in currentRoot.children:
                return False
            currentRoot = currentRoot.children[letter]

        return True

Common Mistakes / Things I Got Stuck On

• Not creating a TrieNode
• syntax regarding __init__ and creating instances of new classes like TrieNode()