LeetCode 208 Implement Trie - Implementation

TrieNode with children map and isEnd flag.

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

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

def insert(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.isEnd = True

def search(self, word):
    node = self._traverse(word)
    return node is not None and node.isEnd

def startsWith(self, prefix):
    return self._traverse(prefix) is not None

def _traverse(self, s):
    node = self.root
    for char in s:
        if char not in node.children:
            return None
        node = node.children[char]
    return node

$O(m)$ per operation.