Prefix Search Using Trie in DSA Typescript - Build from Scratch

Prefix Search Using Trie

📖 Scenario: You are building a simple search feature for a phone contacts app. When a user types some letters, the app should quickly find all contact names that start with those letters.To do this efficiently, you will use a Trie data structure, which stores words by their letters in a tree form.

🎯 Goal: Build a Trie to store contact names and write a function to find all contacts starting with a given prefix.

📋 What You'll Learn

Create a TrieNode class with a children map and an endOfWord boolean

Create a Trie class with insert and searchPrefix methods

Insert given contact names into the Trie

Write a function to find all contacts starting with a given prefix

Print the list of contacts found for the prefix

💡 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 children property as a Map from string to TrieNode and a endOfWord boolean property set to false. Then create a class called Trie with a root property initialized as a new TrieNode. Add an insert method to Trie that takes a word string and inserts it into the trie letter by letter.

DSA Typescript

// Your code here to create TrieNode and Trie classes with insert method

Hint

Think of TrieNode as a box holding letters and a flag if a word ends there. The Trie has a root box and an insert method to add words letter by letter.

2

Insert contact names into the Trie

Create a string array called contacts with these exact names: 'alice', 'alex', 'bob', 'bobby', 'carol'. Then create a Trie instance called trie and insert each contact from contacts into trie using the insert method.

DSA Typescript

class TrieNode {
    children: Map;
    endOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.endOfWord = false;
    }
}

class Trie {
    root: TrieNode;

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

    insert(word: string): void {
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new TrieNode());
            }
            current = current.children.get(char)!;
        }
        current.endOfWord = true;
    }
}

// Create contacts array and insert each into trie
// Your code here

Hint

Make an array with the exact contact names. Then create a Trie and add each contact using the insert method.

3

Add searchPrefix method to find all contacts starting with a prefix

Add a method called searchPrefix to the Trie class. It takes a prefix string and returns a string array of all words in the trie that start with that prefix. Use a helper function inside searchPrefix to recursively collect all words starting from the node matching the prefix.

DSA Typescript

class TrieNode {
    children: Map;
    endOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.endOfWord = false;
    }
}

class Trie {
    root: TrieNode;

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

    insert(word: string): void {
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new TrieNode());
            }
            current = current.children.get(char)!;
        }
        current.endOfWord = true;
    }

    // Add searchPrefix method below
    // Your code here
}

const contacts: string[] = ['alice', 'alex', 'bob', 'bobby', 'carol'];
const trie = new Trie();
for (const contact of contacts) {
    trie.insert(contact);
}

Hint

First find the node matching the prefix. Then use a helper function to explore all children nodes and collect words that end there.

4

Print contacts starting with prefix 'bo'

Use the searchPrefix method of trie to find all contacts starting with the prefix 'bo'. Store the result in a variable called results and print it using console.log(results).

DSA Typescript

class TrieNode {
    children: Map;
    endOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.endOfWord = false;
    }
}

class Trie {
    root: TrieNode;

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

    insert(word: string): void {
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) {
                current.children.set(char, new TrieNode());
            }
            current = current.children.get(char)!;
        }
        current.endOfWord = true;
    }

    searchPrefix(prefix: string): string[] {
        let current = this.root;
        for (const char of prefix) {
            if (!current.children.has(char)) {
                return [];
            }
            current = current.children.get(char)!;
        }

        const results: string[] = [];

        const dfs = (node: TrieNode, path: string) => {
            if (node.endOfWord) {
                results.push(path);
            }
            for (const [char, childNode] of node.children) {
                dfs(childNode, path + char);
            }
        };

        dfs(current, prefix);
        return results;
    }
}

const contacts: string[] = ['alice', 'alex', 'bob', 'bobby', 'carol'];
const trie = new Trie();
for (const contact of contacts) {
    trie.insert(contact);
}

// Your code here to search prefix 'bo' and print results

Hint

Call searchPrefix with 'bo' and print the returned array.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To efficiently find all words that start with a given prefix

B. To sort words alphabetically

C. To store words in reverse order

D. To count the total number of words

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by their prefixes, allowing quick prefix-based lookups.

2. Step 2: Identify prefix search goal

   Prefix search means finding all words starting with a given prefix efficiently.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option A

4. Quick Check:

   Trie = Prefix search [OK]

Hint: Trie is built for prefix-based fast word retrieval [OK]

Common Mistakes:

• Confusing Trie with sorting structure
• Thinking Trie stores words reversed
• Assuming Trie counts total words only

2. Which of the following is the correct TypeScript syntax to define a Trie node with children as a Map and an endOfWord boolean?

easy

A. class TrieNode { children: object; endOfWord: string; constructor() { this.children = {}; this.endOfWord = ''; } }

B. class TrieNode { children: string[]; endOfWord: boolean; constructor() { this.children = []; this.endOfWord = false; } }

C. class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } }

D. class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } }

Solution

1. Step 1: Check children type

   Children should be a Map with string keys and TrieNode values for prefix characters.

2. Step 2: Check endOfWord type

   endOfWord is a boolean indicating if node ends a word.

3. Final Answer:

   class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } } -> Option D

4. Quick Check:

   Map + boolean endOfWord = class TrieNode { children: Map; endOfWord: boolean; constructor() { this.children = new Map(); this.endOfWord = false; } } [OK]

Hint: Use Map for children and boolean for endOfWord [OK]

Common Mistakes:

• Using array instead of Map for children
• Using wrong key type in Map
• Setting endOfWord as string instead of boolean

3. Given the following TypeScript code snippet, what will be the output of console.log(trie.startsWith('app'))?

class TrieNode {
  children = new Map();
  endOfWord = false;
}

class Trie {
  root = new TrieNode();

  insert(word: string) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.endOfWord = true;
  }

  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return false;
      node = node.children.get(char)!;
    }
    return true;
  }
}

const trie = new Trie();
trie.insert('apple');
trie.insert('app');
trie.insert('bat');

medium

A. true

B. false

C. undefined

D. Error at runtime

Solution

1. Step 1: Insert words into Trie

   Words 'apple', 'app', and 'bat' are inserted, so prefix 'app' exists in Trie.

2. Step 2: Check startsWith method

   Method returns true if prefix characters exist in Trie nodes, which they do for 'app'.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Prefix 'app' found = true [OK]

Hint: If prefix inserted, startsWith returns true [OK]

Common Mistakes:

• Confusing startsWith with search for whole word
• Expecting false if prefix is a word itself
• Thinking startsWith returns endOfWord status

4. The following TypeScript code tries to implement a startsWith method for a Trie but always returns false. What is the bug?

startsWith(prefix: string): boolean {
  let node = this.root;
  for (const char of prefix) {
    if (!node.children.has(char)) return false;
    node = node.children.get(char);
  }
  return false;
}

medium

A. It should check endOfWord before returning

B. It should use a for loop with index instead of for-of

C. It should return true after the loop if prefix exists

D. It should initialize node with a new TrieNode

Solution

1. Step 1: Analyze loop behavior

   The loop correctly traverses nodes for each prefix character.

2. Step 2: Check return statement

   Method returns false always after loop, so never returns true even if prefix found.

3. Step 3: Fix return logic

   Return true after loop if all prefix chars found.

4. Final Answer:

   It should return true after the loop if prefix exists -> Option C

5. Quick Check:

   Return true after loop if prefix found [OK]

Hint: Return true after loop if prefix nodes exist [OK]

Common Mistakes:

• Returning false at end regardless
• Checking endOfWord unnecessarily
• Incorrect node initialization

5. You want to extend a Trie to return all words starting with a given prefix. Which approach correctly implements this in TypeScript? A) Traverse to prefix node, then recursively collect all words below. B) Store all words in an array and filter by prefix each time. C) Use a hash map to map prefixes to words directly. D) Insert reversed words and search suffixes instead.

hard

A. Store all words in an array and filter by prefix each time.

B. Traverse to prefix node, then recursively collect all words below.

C. Use a hash map to map prefixes to words directly.

D. Insert reversed words and search suffixes instead.

Solution

1. Step 1: Understand prefix search extension

   To get all words with prefix, first find node matching prefix.

2. Step 2: Collect words recursively

   From prefix node, recursively traverse children to collect all complete words.

3. Step 3: Evaluate other options

   Filtering array or hash map is less efficient; reversed words search suffixes, not prefixes.

4. Final Answer:

   Traverse to prefix node, then recursively collect all words below. -> Option B

5. Quick Check:

   Recursive traversal from prefix node = Traverse to prefix node, then recursively collect all words below. [OK]

Hint: Find prefix node, then DFS to collect words [OK]

Common Mistakes:

• Filtering all words each time (slow)
• Using hash map without prefix traversal
• Confusing prefix with suffix search