Longest Word in Dictionary Using Trie in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Word Found Using Trie

What is the output of the following code that builds a trie from a list of words and finds the longest word where all prefixes are also words?

DSA Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = 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.is_word = True

    def longest_word(self):
        result = ""
        stack = [(self.root, "")]
        while stack:
            node, path = stack.pop()
            if node.is_word or node == self.root:
                if len(path) > len(result) or (len(path) == len(result) and path < result):
                    result = path
                for char in sorted(node.children.keys(), reverse=True):
                    stack.append((node.children[char], path + char))
        return result

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

A "apply"

B "apple"

C "app"

D "appl"

💡 Hint

Check which words have all prefixes present in the list.

The longest word where all prefixes are words is "apple" because "a", "ap", "app", "appl", "apple" are all present. Both "apple" and "apply" qualify since all their prefixes are words, but "apple" is lexicographically smaller.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the role of the 'is_word' attribute in a trie node when finding the longest word in a dictionary?

A It counts how many words pass through this node.

B It stores the character value of the node.

C It marks whether the path to this node forms a complete valid word in the dictionary.

D It indicates if the node has any children nodes.

💡 Hint

Think about how to know if a prefix is a valid word.

The 'is_word' attribute is True if the path from the root to this node forms a complete word in the dictionary. This helps to check if all prefixes exist when searching for the longest word.

🔧 Debug

advanced

Identify the Bug in Trie Longest Word Search

The following code attempts to find the longest word in a dictionary using a trie, but it returns an empty string. What is the bug?

DSA Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = 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.is_word = True

    def longest_word(self):
        result = ""
        stack = [(self.root, "")]
        while stack:
            node, path = stack.pop()
            if node.is_word or node == self.root:
                if len(path) > len(result) or (len(path) == len(result) and path < result):
                    result = path
                for char in sorted(node.children.keys(), reverse=True):
                    stack.append((node.children[char], path + char))
        return result

words = ["a", "ap", "app", "apple", "apply"]
trie = Trie()
for w in words:
    trie.insert(w)
print(trie.longest_word())

A The insert method does not mark the last node as a word.

B The children are not sorted correctly, causing the wrong word to be chosen.

C The stack is not initialized with the root node.

D The root node is not considered a valid starting point because it is not marked as a word.

💡 Hint

Check the condition that allows traversal from the root node.

The root node is not marked as a word, so the search never starts from it. The condition 'if node.is_word' skips the root node, which prevents any traversal and results in an empty string.

🚀 Application

advanced

Longest Word with All Prefixes Present

Given the list of words ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"], which word will be returned by a trie-based algorithm that finds the longest word where every prefix is also a word?

A "world"

B "banana"

C "banan"

D "worl"

💡 Hint

Check which words have all prefixes present in the list.

"world" is the longest word where all prefixes ("w", "wo", "wor", "worl", "world") are present. "banana" is not valid because prefixes like "b" and "ba" are not present in the list.

🧠 Conceptual

expert

Why Use DFS with Stack in Trie Longest Word Search?

Why does the trie-based longest word search algorithm use a stack and depth-first search (DFS) instead of breadth-first search (BFS)?

A DFS with a stack allows checking longer words first and updating the result immediately, ensuring lexicographically smallest word is found when lengths tie.

B BFS would find the longest word faster because it explores all nodes at the same depth first.

C DFS uses less memory than BFS because it stores fewer nodes at a time, which is critical for large tries.

D BFS cannot be used with tries because it does not support prefix checking.

💡 Hint

Consider how the algorithm prioritizes longer words and lex order.

Using DFS with a stack and sorting children in reverse lexicographical order allows the algorithm to explore longer words first and update the result accordingly. This ensures the longest word with the smallest lexicographical order is found.

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"