Build trie, then BFS to find the longest valid word:
def longestWord(words):
trie = Trie()
for word in words:
trie.insert(word)
result = ""
queue = [trie.root]
while queue:
node = queue.pop(0)
for c in sorted(node.children.keys()):
child = node.children[c]
if child.isEnd:
word = child.word # stored during insert
if len(word) > len(result):
result = word
queue.append(child)
return result
BFS explores level by level. You only continue to a child if it marks a complete word—ensuring every prefix exists. Sorting children gives lexicographic order.
Time: for building trie, for BFS. Space: .