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.