Longest Word Solution

Build trie, then BFS to find the longest valid word:

function longestWord(words):
    trie = Trie()
    for word in words:
        trie.insert(word)

    result = ""
    queue = [trie.root]

    while queue:
        node = queue.dequeue()
        for c in sorted(node.children.keys()):
            child = node.children[c]
            if child.isEnd:
                word = child.word // stored during insert
                if word.length > result.length:
                    result = word
                queue.append(child)

    return result

BFS explores level by level. You only continue to a child if it marks a complete word. This ensures every prefix exists. Sorting children gives lexicographic order.

Time: $O(\sum |w|)$ for building trie, $O(n)$ for BFS. Space: $O(\sum |w|)$.