Longest Word in Dictionary Using Trie in DSA Javascript - Build from Scratch

Longest Word in Dictionary Using Trie

📖 Scenario: Imagine you have a list of words from a dictionary. You want to find the longest word that can be built one character at a time by other words in the list. For example, if the word is "apple", then "a", "ap", "app", "appl" must also be in the list.

🎯 Goal: You will build a Trie data structure to store the words. Then, you will write code to find the longest word that can be built character by character from other words in the dictionary.

📋 What You'll Learn

Create a TrieNode class with children and endOfWord properties

Create a Trie class with insert and search methods

Insert all words from the given list into the Trie

Find the longest word that can be built one character at a time using the Trie

Print the longest word found

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and word games to quickly find words and prefixes.

💼 Career

Understanding Tries and prefix searches is useful for software engineers working on search engines, text processing, and data compression.

1

Create TrieNode and Trie classes

Create a class called TrieNode with a constructor that initializes children as an empty object and endOfWord as false. Then create a class called Trie with a constructor that initializes root as a new TrieNode.

DSA Javascript

// Create TrieNode class
// Create Trie class with root property
// Your code here

Hint

Think of TrieNode as a box that can hold other boxes (children) and a flag to say if a word ends here.

2

Add insert method to Trie

Add an insert method to the Trie class that takes a word string. Use a variable node starting at this.root. For each character in word, if the character is not in node.children, create a new TrieNode for it. Move node to the child node. After the loop, set node.endOfWord to true.

DSA Javascript

class TrieNode {
    constructor() {
        this.children = {};
        this.endOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // Add insert method here
    // Your code here
}

Hint

Insert each character step by step, creating new nodes if needed, and mark the end of the word.

3

Insert words and find longest buildable word

Create a variable words with the array ["a", "ap", "app", "appl", "apple", "apply"]. Create a Trie instance called trie. Insert each word from words into trie using the insert method. Then create a function longestWord that takes words and trie. It should find the longest word where every prefix is also a word in the trie. Use a helper function to check prefixes. Return the longest such word.

DSA Javascript

class TrieNode {
    constructor() {
        this.children = {};
        this.endOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.endOfWord = true;
    }
}

// Create words array and insert words into trie
// Create longestWord function
// Your code here

Hint

Check each word's prefixes by walking the trie. Keep track of the longest valid word.

4

Print the longest word

Call the longestWord function with words and trie. Print the returned longest word using console.log.

DSA Javascript

class TrieNode {
    constructor() {
        this.children = {};
        this.endOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.endOfWord = true;
    }
}

const words = ["a", "ap", "app", "appl", "apple", "apply"];
const trie = new Trie();
for (const word of words) {
    trie.insert(word);
}

function longestWord(words, trie) {
    let longest = "";

    function canBuild(word) {
        let node = trie.root;
        for (const char of word) {
            node = node.children[char];
            if (!node || !node.endOfWord) {
                return false;
            }
        }
        return true;
    }

    for (const word of words) {
        if (canBuild(word)) {
            if (word.length > longest.length || (word.length === longest.length && word < longest)) {
                longest = word;
            }
        }
    }
    return longest;
}

// Print the longest word
// Your code here

Hint

Use console.log(longestWord(words, trie)) to print the result.

Practice

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

easy

A. To reverse the words in the dictionary

B. To sort words alphabetically

C. To count the total number of words

D. To efficiently store and search words by their prefixes

Solution

1. Step 1: Understand Trie usage

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

2. Step 2: Connect 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 D

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is all about prefixes and fast word lookup [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie reverses words
• Assuming Trie counts words only

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

easy

A. node[word[i]] = new TrieNode() if not exists

B. node[word[i]] = word[i]

C. node.push(word[i])

D. node[word] = true

Solution

1. Step 1: Understand Trie node insertion

   Each character of the word is a key in the node object; if missing, create a new TrieNode.

2. Step 2: Identify correct syntax

   Using node[word[i]] = new TrieNode() creates a child node for that character if it doesn't exist.

3. Final Answer:

   node[word[i]] = new TrieNode() if not exists -> Option A

4. Quick Check:

   Insert char as child node [OK]

Hint: Insert chars as keys with new nodes if missing [OK]

Common Mistakes:

• Assigning character directly instead of node
• Using array push on object
• Setting whole word as key instead of chars

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. "apple"

B. "apply"

C. "app"

D. "ap"

Solution

1. Step 1: Check each word buildability

   Words must be built one char at a time with all prefixes present. "a", "ap", "app" are present, but "apple" and "apply" require "appl" which is missing.

2. Step 2: Identify longest valid word

   "app" is the longest word where all prefixes ("a", "ap", "app") exist in the list.

3. Final Answer:

   "app" -> Option C

4. Quick Check:

   Longest buildable word = "app" [OK]

Hint: Check all prefixes exist for each candidate word [OK]

Common Mistakes:

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

4. What is the bug in this Trie insertion snippet for finding the longest word?

for (let char of word) {
  if (!node[char]) {
    node[char] = {};
  }
  node = node[char];
}
node.isWord = true;

medium

A. No bug, code is correct

B. Missing initialization of root node

C. Not marking the end of word properly

D. Using plain object instead of TrieNode class

Solution

1. Step 1: Analyze insertion logic

   The loop creates child nodes if missing and moves down the Trie correctly.

2. Step 2: Check end of word marking

   Setting node.isWord = true marks the end of the word properly.

3. Final Answer:

   No bug, code is correct -> Option A

4. Quick Check:

   Insertion and marking done correctly [OK]

Hint: Mark end of word after insertion loop [OK]

Common Mistakes:

• Forgetting to mark end of word
• Overcomplicating node creation
• Assuming class needed when object works

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

hard

A. "banan"

B. "world"

C. "banana"

D. "worl"

Solution

1. Step 1: Verify prefix existence for each candidate

   For "world": prefixes "w", "wo", "wor", "worl", "world" all exist. For "banana": prefixes "b", "ba", "ban", "bana", "banan", "banana" -- but "b" and "ba" are missing. Similarly, "banan" misses "b" and "ba".

2. Step 2: Compare longest buildable words

   "world" is the longest word where all prefixes from length 1 to full length exist in the list.

3. Final Answer:

   "world" -> Option B

4. Quick Check:

   Longest buildable word = "world" [OK]

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

Common Mistakes:

• Choosing "banana" without all prefixes
• Ignoring missing prefixes
• Confusing partial prefixes as complete