Q65: Implement Trie (Prefix Tree). - DSA Patterns (Multi-Lang)

In Simple Words: N-ary tree where each node has a children map (or array of 26) and a boolean isEndOfWord.

insert: walk or create nodes, mark end.
search: walk nodes, verify node.isEndOfWord.
startsWith: walk nodes, return true if prefix path exists.
Time: $O(L)$ per operation | Space: $O(N \cdot L)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

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

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

    def insert(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.is_end = True

    def search(self, word: str) -> bool:
        curr = self.root
        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return curr.is_end

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for c in prefix:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return True