Prefix Search Using Trie in DSA Typescript

Mental Model

A trie stores words by sharing common starting letters, making it easy to find all words starting with a prefix quickly.

Analogy: Imagine a tree where each branch is a letter, and paths from the root to leaves form words. To find words starting with a prefix, you just follow the branch for each letter of the prefix, then collect all words below.

root
 ↓
 t -> r -> i -> e
 ↑
 prefix start

Dry Run Walkthrough

Input: words: ["tree", "trie", "algo", "assoc", "all", "also"], prefix: "tr"

Goal: Find all words in the trie that start with the prefix "tr"

Step 1: Insert word "tree" letter by letter into trie

root -> t -> r -> e -> e [end]
other branches empty

Why: Build trie nodes for each letter to store the word

Step 2: Insert word "trie" sharing prefix "tr" nodes

root -> t -> r -> e -> e [end]
               ↓
               i -> e [end]

Why: Reuse existing nodes for 't' and 'r' to save space

Step 3: Insert other words "algo", "assoc", "all", "also" creating separate branches

root -> t -> r -> e -> e [end]
               ↓
               i -> e [end]
  ↓
  a -> l -> g -> o [end]
    ↓
    s -> s -> o -> c [end]
    ↓
    l -> l [end]
    ↓
    s -> o [end]

Why: Add new branches for words with different starting letters

Step 4: Search prefix "tr" by following nodes t -> r

At node 'r' after prefix traversal

Why: Locate the node where prefix ends to find all words below

Step 5: Collect all words below node 'r': "tree", "trie"

Collected words: ["tree", "trie"]

Why: All words starting with prefix are in this subtree

Result:

root -> t -> r -> e -> e [end]
               ↓
               i -> e [end]
Words with prefix 'tr': ["tree", "trie"]

Annotated Code

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    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)!; // advance node to child
    }
    node.isEndOfWord = true; // mark end of word
  }

  searchPrefix(prefix: string): TrieNode | null {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return null; // prefix not found
      }
      node = node.children.get(char)!; // advance node
    }
    return node; // node at end of prefix
  }

  collectAllWords(node: TrieNode | null, prefix: string, words: string[]): void {
    if (!node) return;
    if (node.isEndOfWord) {
      words.push(prefix); // found a word
    }
    for (const [char, childNode] of node.children) {
      this.collectAllWords(childNode, prefix + char, words); // recurse children
    }
  }

  getWordsWithPrefix(prefix: string): string[] {
    const node = this.searchPrefix(prefix);
    if (!node) return [];
    const words: string[] = [];
    this.collectAllWords(node, prefix, words);
    return words;
  }
}

// Driver code
const trie = new Trie();
const words = ["tree", "trie", "algo", "assoc", "all", "also"];
for (const word of words) {
  trie.insert(word);
}
const prefix = "tr";
const result = trie.getWordsWithPrefix(prefix);
console.log(`Words with prefix '${prefix}': ["${result.join('", "')}"]`);

node = this.root;

start from root to insert or search

if (!node.children.has(char)) { node.children.set(char, new TrieNode()); }

create new node if letter path does not exist

node = node.children.get(char)!;

advance node to next letter in word or prefix

node.isEndOfWord = true;

mark node as end of a valid word

if (!node.children.has(char)) { return null; }

stop search if prefix letter missing

if (node.isEndOfWord) { words.push(prefix); }

collect word when end of word node reached

this.collectAllWords(childNode, prefix + char, words);

recursively collect all words under current node

Output

Words with prefix 'tr': ["tree", "trie"]

Complexity Analysis

Time: O(m + k) where m is length of prefix and k is total letters in subtree words; prefix search takes O(m), collecting words depends on subtree size

Space: O(n * l) where n is number of words and l is average word length for trie storage; output space depends on number of matched words

vs Alternative: Compared to scanning all words for prefix match O(n*l), trie reduces prefix search to O(m) plus subtree traversal, which is faster for large datasets

Edge Cases

Empty prefix string

Returns all words stored in trie

DSA Typescript

const node = this.searchPrefix(prefix);

Prefix not present in trie

Returns empty list since searchPrefix returns null

DSA Typescript

if (!node) return [];

Words with shared prefix but different lengths

All words starting with prefix are collected correctly

DSA Typescript

if (node.isEndOfWord) { words.push(prefix); }

When to Use This Pattern

When you need to quickly find all words starting with a prefix, use a trie because it organizes words by shared prefixes for fast lookup.

Common Mistakes

Mistake: Not marking the end of word node, causing incomplete word detection
Fix: Set isEndOfWord = true at the last node of each inserted word

Mistake: Returning null without handling it in getWordsWithPrefix, causing errors
Fix: Check if searchPrefix returns null and handle by returning empty list

Summary

Stores words in a tree structure to quickly find all words starting with a given prefix.

Use when you want efficient prefix-based search among many words.

Follow prefix nodes then collect all words below to get all matches.

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