Longest Word in Dictionary Using Trie in DSA Python

Mental Model

We build a tree of letters from all words, then find the longest word where every prefix is also a word.

Analogy: Imagine a family tree where each generation is a letter, and only branches where every ancestor is known are valid paths to the longest name.

root
 ↓
 t -> r -> i -> e
 ↑    ↑    ↑    ↑
end  end  end  end

Each node points to next letter; 'end' marks a complete word.

Dry Run Walkthrough

Input: words = ["a", "app", "ap", "apply", "apple", "appl"]

Goal: Find the longest word where all prefixes are also words in the list.

Step 1: Insert 'a' into trie, mark end at 'a'

root -> a[end]
Only one word inserted

Why: Start building trie with first word

Step 2: Insert 'app' into trie, mark end at 'p'

root -> a[end] -> p -> p[end]
Prefixes 'a' and 'app' marked

Why: Add longer word sharing prefix 'a'

Step 3: Insert 'ap' into trie, mark end at 'p'

root -> a[end] -> p[end] -> p[end]
Prefixes 'a', 'ap', 'app' marked

Why: Mark prefix 'ap' as word to allow longer words

Step 4: Insert 'apply' into trie, mark end at 'y'

root -> a[end] -> p[end] -> p[end] -> l -> y[end]
Longer word added

Why: Add longer word with all prefixes present

Step 5: Insert 'apple' into trie, mark end at 'e'

root -> a[end] -> p[end] -> p[end] -> l -> e[end]
Another long word added

Why: Add another long word with prefixes

Step 6: Insert 'appl' into trie, mark end at 'l'

root -> a[end] -> p[end] -> p[end] -> l[end]
Prefix for 'apple' and 'apply' marked

Why: Mark prefix 'appl' as word to allow longer words

Step 7: Search trie for longest word where all prefixes are words

Check words: 'a', 'ap', 'app', 'appl', 'apple', 'apply'
'apple' and 'apply' qualify

Why: Find longest word with all prefixes present

Step 8: Choose lexicographically smallest among longest words

Between 'apple' and 'apply', 'apple' is chosen

Why: Tie-break by alphabetical order

Result:

root -> a[end] -> p[end] -> p[end] -> l[end] -> e[end]
Longest word: apple

Annotated Code

DSA Python

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

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

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

    def longest_word(self) -> str:
        result = ""
        def dfs(node, path):
            nonlocal result
            if node != self.root and not node.end_of_word:
                return
            if len(path) > len(result) or (len(path) == len(result) and path < result):
                result = path
            for char in sorted(node.children.keys()):
                dfs(node.children[char], path + char)
        dfs(self.root, "")
        return result

if __name__ == "__main__":
    words = ["a", "app", "ap", "apply", "apple", "appl"]
    trie = Trie()
    for word in words:
        trie.insert(word)
    print(trie.longest_word())

for char in word:

Traverse or create nodes for each letter in the word

node.end_of_word = True

Mark the last node as end of a valid word

if node != self.root and not node.end_of_word: return

Stop DFS if current prefix is not a complete word

if len(path) > len(result) or (len(path) == len(result) and path < result): result = path

Update longest word if current path is longer or lex smaller

for char in sorted(node.children.keys()): dfs(node.children[char], path + char)

Explore children in alphabetical order to ensure lex order

Output

apple

Complexity Analysis

Time: O(N * L) where N is number of words and L is max word length because we insert all words and DFS all nodes once

Space: O(N * L) for trie storage holding all characters of all words

vs Alternative: Compared to sorting and checking prefixes directly (O(N log N * L)), trie allows prefix checks efficiently during DFS

Edge Cases

Empty list of words

Returns empty string as no words exist

DSA Python

if node != self.root and not node.end_of_word:
    return

Words with no valid prefixes except single letters

Returns the longest single-letter word

DSA Python

if node != self.root and not node.end_of_word:
    return

Multiple longest words with same length

Returns lexicographically smallest among them

DSA Python

if len(path) > len(result) or (len(path) == len(result) and path < result):
    result = path

When to Use This Pattern

When asked to find the longest word where all prefixes are valid words, use a trie to efficiently check prefixes during traversal.

Common Mistakes

Mistake: Not checking if all prefixes are words before extending path
Fix: Add condition to stop DFS if current prefix is not marked as end_of_word

Mistake: Not sorting children keys leading to incorrect lexicographical order
Fix: Sort children keys before DFS to ensure lex order

Summary

Build a trie from words and find the longest word where every prefix is also a word.

Use when you need to find words with prefix constraints efficiently.

The key is to stop exploring paths where prefixes are not complete words and to explore children in alphabetical order.

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To count the total number of words

D. To reverse the words in the dictionary

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by breaking them into characters and linking nodes for prefixes.

2. Step 2: Relate Trie to longest word search

   This structure allows quick prefix checks, which helps find the longest word built from other words.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with simple lists
• Assuming Trie counts words only

2. Which of the following is the correct way to insert a word into a Trie node in Python?

easy

A. node.children[char] = TrieNode() if char not in node.children else node.children[char]

B. node.children.add(char)

C. node.children.append(char)

D. node.children[char] = char

Solution

1. Step 1: Understand Trie children structure

   Trie children are stored in a dictionary mapping characters to TrieNode objects.

2. Step 2: Correct insertion method

   We check if character exists; if not, create new TrieNode and assign it to children dictionary.

3. Final Answer:

   node.children[char] = TrieNode() if char not in node.children else node.children[char] -> Option A

4. Quick Check:

   Insert uses dictionary with TrieNode [OK]

Hint: Use dictionary keys for children, not list or set [OK]

Common Mistakes:

• Using add() or append() on dictionary
• Assigning character instead of TrieNode
• Not checking if child exists before insertion

3. Given the words: ["a", "app", "apple", "apply", "ap"], what is the longest word that can be built one character at a time using the Trie method?

medium

A. "apply"

B. "app"

C. "apple"

D. "ap"

Solution

1. Step 1: Check each word's prefixes

   Words must have all prefixes present: "a", "ap", "app" are present; "apple" and "apply" require "appl" which is missing.

2. Step 2: Identify longest valid word

   "app" is the longest word where all prefixes exist in the list.

3. Final Answer:

   "app" -> Option B

4. Quick Check:

   Longest word with all prefixes = "app" [OK]

Hint: Check all prefixes exist before choosing longest word [OK]

Common Mistakes:

• Assuming "apple" or "apply" are valid without "appl"
• Ignoring prefix requirement
• Choosing shortest word instead

4. What is the error in this Trie insertion code snippet for building the longest word?

for word in words:
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode
        node = node.children[char]
    node.is_word = True

medium

A. The root node should be reset after each character

B. The loop should iterate over characters in reverse

C. node.is_word should be set before the inner loop

D. TrieNode should be called with parentheses to create an instance

Solution

1. Step 1: Identify object creation mistake

   TrieNode is a class; to create an object, parentheses () are needed.

2. Step 2: Understand impact of missing parentheses

   Without (), node.children[char] stores the class itself, not an instance, causing errors on further access.

3. Final Answer:

   TrieNode should be called with parentheses to create an instance -> Option D

4. Quick Check:

   Instantiate TrieNode with () [OK]

Hint: Always use () to create class instances in Python [OK]

Common Mistakes:

• Forgetting parentheses when creating objects
• Setting flags in wrong loop place
• Resetting root incorrectly inside loops

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word will be returned as the longest word built one character at a time from other words in the list?

hard

A. "worl"

B. "banana"

C. "world"

D. "banan"

Solution

1. Step 1: Verify prefix chains for each candidate

   "world" prefixes: "w", "wo", "wor", "worl", "world" all exist; "banana" and "banan" missing prefixes like "b", "ba"; "worl" is shorter than "world".

2. Step 2: Choose longest word with all prefixes present

   "world" is longest with all prefixes present in the list.

3. Final Answer:

   "world" -> Option C

4. Quick Check:

   Longest word with full prefix chain = "world" [OK]

Hint: Check full prefix chain exists before longest word [OK]

Common Mistakes:

• Choosing "banana" without full prefix chain
• Ignoring prefix requirement for "banan"
• Picking shorter word "worl" over "world"