Implementing a Trie in TypeScript: Solving 'Implement Trie (Prefix Tree)'

Trie questions can look more exotic than they really are because the name sounds more specialised than the underlying idea. A trie is just a tree that stores words by shared prefix. That means words with the same opening characters reuse the same path instead of storing that prefix over and over again.

So if we insert:

• cat
• car
• care

the c ‑> a part is shared. Only the later branches diverge.

That sharing is the entire point.

A Simple Alternative Exists, but It is Not the Right Lesson

Before reaching for a trie, we could absolutely solve the LeetCode interface with two sets:

• one set for full words
• one set for all prefixes we have inserted

class Trie {  private readonly words = new Set<string>();  private readonly prefixes = new Set<string>();  public insert(word: string): void {    this.words.add(word);    for (let index = 1; index <= word.length; index += 1) {      this.prefixes.add(word.slice(0, index));    }  }  public search(word: string): boolean {    return this.words.has(word);  }  public startsWith(prefix: string): boolean {    return this.prefixes.has(prefix);  }}

That works. It is also a bit blunt.

The trouble is that it stores every prefix as its own complete string. For a trie problem, that misses the whole structural idea we are meant to learn.

Why the Trie Structure is a Better Fit

The interface asks for three operations:

• insert
• search
• startsWith

All three are naturally about walking character by character. That makes a node‑per‑character structure a very clean fit.

The useful question becomes:

• can we follow this character path through the tree?

If yes, then:

• search succeeds only if the final node marks the end of a word
• startsWith succeeds as soon as the path exists

A practical Map‑based trie in TypeScript

class TrieNode {  public readonly children = new Map<string, TrieNode>();  public isWord = false;}export class Trie {  private readonly root = new TrieNode();  public insert(word: string): void {    let node = this.root;    for (const character of word) {      const nextNode = node.children.get(character) ?? new TrieNode();      node.children.set(character, nextNode);      node = nextNode;    }    node.isWord = true;  }  public search(word: string): boolean {    const node = this.findNode(word);    return node?.isWord ?? false;  }  public startsWith(prefix: string): boolean {    return this.findNode(prefix) !== null;  }  private findNode(value: string): TrieNode | null {    let node = this.root;    for (const character of value) {      const nextNode = node.children.get(character);      if (!nextNode) {        return null;      }      node = nextNode;    }    return node;  }}

Why This Layout Reads Well

There are only two pieces of state in each node:

• children
• isWord

That is refreshingly small.

The children map tells us where we can go next. The isWord flag tells us whether stopping at this node counts as a complete inserted word.

That distinction matters because:

• car can be a full word
• care can also be a full word

So we cannot treat "path exists" and "word exists" as the same thing.

Why startsWith is cheaper than people sometimes assume

With a trie, startsWith('car') does not need to scan every stored word and ask whether it starts with that prefix. It just walks:

• c
• a
• r

If that path exists, the answer is true.

That is the reason tries are so often introduced in autocomplete and dictionary‑style questions. The lookup cost depends on the length of the query, not on the number of stored words.

Map versus plain object for children

There is a smaller design choice inside the trie too. We could store children as:

• a Map<string, TrieNode>
• a plain object such as Record<string, TrieNode>

The plain‑object version is workable:

type TrieNode = {  children: Record<string, TrieNode>;  isWord: boolean;};

I still prefer Map here for a few reasons:

• the intent is clearer: this is a lookup structure
• we avoid prototype awkwardness
• methods like get, set, and has make the traversal code read cleanly

The object version can be a little lighter in raw syntax, especially if the character set is tightly controlled. In TypeScript, though, Map usually feels like the cleaner editorial choice.

Comparing the Options Properly

So there are really three choices worth mentioning:

1. Set of words plus Set of prefixes

This is the easiest to derive, but it duplicates string storage and teaches less.

1. Trie with plain‑object children

This is valid and can be perfectly fine in some codebases.

1. Trie with Map children

This is my preferred version for a TypeScript guide because the traversal code stays clear and the node shape is explicit.

For this article, I think the Map‑based trie is the best answer overall. The set‑based approach is a decent warm‑up, not a satisfying final solution.

A small example makes the isWord flag make sense

Insert:

• app
• apple

Now search for:

• app
• appl

Both paths exist up to their final character, but only app should return true for search.

That is why the final node needs an explicit end‑of‑word marker. Otherwise the trie cannot tell:

• full stored word

from:

• prefix of a longer stored word

Complexity and Where the Trie Earns Its Keep

If the input word length is m, then:

• insert is O(m)
• search is O(m)
• startsWith is O(m)

That is the tidy part. The less tidy part is space. Tries can use a lot of nodes when many words are stored, especially if prefixes are not shared much.

That is why a trie is not automatically the right answer in every application. Sometimes a simple set of strings is enough. But for a prefix‑tree question, the trie is the right conceptual answer because prefix sharing is the whole point of the data structure.

Common Mistakes

Treating "Path Exists" as Equivalent to "Word Exists"

That breaks cases where one word is a prefix of another.

Recreating Traversal Logic Separately in Every Method

Using a helper like findNode keeps search and startsWith much calmer.

Dismissing the Set‑Based Approach as Nonsense

It is not nonsense. It is just less interesting and usually less space‑efficient for the actual job.

The Data‑Structure Lesson Underneath It

Trie problems are a good reminder that some data structures exist to make one kind of repeated question cheap:

• do we have this exact word?
• do we have anything that starts like this?

Once we see the repeated prefix lookup clearly, the structure stops feeling niche.

The Part Worth Remembering

• A trie stores words by shared prefixes rather than as unrelated strings.
• search and startsWith differ because complete words need an explicit end marker.
• A Map‑based trie is the clearest TypeScript implementation here, even though set‑based and object‑based alternatives exist.

Implement Trie is a good data‑structure problem because it rewards building the shape that matches the question instead of forcing every lookup through the same flat string container.