Prefix Search Using Trie in DSA Javascript - Build from Scratch

Prefix Search Using Trie

📖 Scenario: Imagine you have a list of words and want to quickly find all words that start with a certain prefix, like searching names in your phone contacts.

🎯 Goal: You will build a simple Trie data structure to store words and then search for all words starting with a given prefix.

📋 What You'll Learn

Create a TrieNode class with a children object and a boolean isEndOfWord

Create a Trie class with insert(word) and startsWith(prefix) methods

Insert given words into the trie

Search and return all words starting with the given prefix

Print the list of words found by prefix search

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words starting with certain letters.

💼 Career

Understanding Tries helps in roles involving search optimization, text processing, and building efficient data retrieval systems.

1

Create TrieNode and Trie classes

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

DSA Javascript

// Your code here

Hint

Think of TrieNode as a box holding letters and a flag if a word ends there. Trie starts with an empty root node.

2

Add insert method to Trie

Add a method called insert(word) to the Trie class. It should start from this.root and for each character in word, create a new TrieNode in children if it does not exist. After the last character, set isEndOfWord to true.

DSA Javascript

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

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

    // Your code here
}

Hint

Walk through each letter of the word, add nodes if missing, and mark the end of the word.

3

Add startsWith method to find words by prefix

Add a method called startsWith(prefix) to the Trie class. It should find the node matching the last character of prefix. Then collect all words starting from that node by traversing children recursively. Return the list of words with the prefix included.

DSA Javascript

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

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

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

    // Add startsWith method below
}

Hint

First find the node for the prefix, then explore all child nodes to collect full words.

4

Insert words and print prefix search results

Create a Trie instance called trie. Insert these words exactly: 'apple', 'app', 'apricot', 'banana'. Then print the result of trie.startsWith('ap').

DSA Javascript

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

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

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

    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return [];
            }
            node = node.children[char];
        }

        const words = [];

        function dfs(currentNode, path) {
            if (currentNode.isEndOfWord) {
                words.push(path);
            }
            for (let childChar in currentNode.children) {
                dfs(currentNode.children[childChar], path + childChar);
            }
        }

        dfs(node, prefix);
        return words;
    }
}

// Your code here

Hint

Insert the words exactly, then print the list of words starting with 'ap'. The output should be an array of matching words.