class Trie(object): def __init__(self, value=None): self.children = {} self.value = value self.flag = False # Flag to indicate that a word ends at this node def add(self, char): val = self.value + char if self.value else char self.children[char] = Trie(val) def insert(self, word): node = self for char in word: if char not in node.children: node.add(char) node = node.children[char] node.flag = True def find(self, word): node = self for char in word: if char not in node.children: return None node = node.children[char] return node.value