Trie | Data structure implementation in Typescript

In my projects I work a lot with list of words. If you ever have to deal with words and texts, you will eventually discover (and implement) a Trie data structure.

This is what happened to me. I ended up implementing a Trie in various languages and with different strategies.

Finally, I settled on one implementation that is efficient and complete (complete enough for my purposes).

Here it is 👇

trie.ts

export class Trie {
  /** Check if the current node marks a complete word */
  #isEnd = false;

  /** Store sub-`Trie` */
  #children: Record<string, Trie> = {};

  constructor() {}

  public get isEnd() {
    return this.#isEnd;
  }

  public get children() {
    return this.#children;
  }

  /**
   * Check if given `char` is present in current `Trie`.
   */
  hasChar(char: string): Trie | null {
    const searchChar = this.children[char];
    if (typeof searchChar !== "undefined") {
      return searchChar;
    }

    return null;
  }

  /**
   * Add `Trie` at given `char`, and return new added `Trie`.
   */
  addChar(char: string): Trie {
    const newSubTrie = new Trie();
    this.children[char] = newSubTrie;
    return newSubTrie;
  }

  /**
   * Mark complete word found in current `Trie`.
   */
  makeEnd(): void {
    this.#isEnd = true;
  }

  /**
   * Search given `word` in `Trie`.
   */
  searchTrie(word: string): boolean {
    if (word.length === 0) {
      return this.#isEnd;
    }

    const subTrie = this.hasChar(word[0]);
    if (subTrie === null) {
      return false;
    }

    return subTrie.searchTrie(word.slice(1));
  }

  /**
   * Add `word` to this `Trie`.
   */
  addWord(word: string): void {
    if (word.length === 0) {
      this.makeEnd();
      return;
    }

    const subTrie = this.hasChar(word[0]);
    if (subTrie !== null) {
      return subTrie.addWord(word.slice(1));
    } else {
      const newSubTrie = this.addChar(word[0]);
      return newSubTrie.addWord(word.slice(1));
    }
  }

  /**
   * Static constructor to build a `Trie` from a list of words (`wordList`).
   */
  static buildTrie = (wordList: string[]): Trie => {
    const trie = new Trie();
    for (let i = 0; i < wordList.length; i++) {
      const word = wordList[i];
      trie.addWord(word);
    }

    return trie;
  };
}

What is a `Trie`?

A Trie is a data structure used to store a list of words. Using a Trie makes searching for a word efficient (O(dm), where d is the length of the string you are searching, and m is the alphabet size).

When to use a `Trie`

Following a simple usecase example.

You have a list of words and a long text, and you want to search all the occurrences of each word in the text.

The naive / brute-force approach consists splitting the text in words and, for each word, search in the list. This gets slow pretty fast 🙌

In this case a Trie is ideal, since it stores words more efficiently and it makes searching much faster 🏎️

How to use `Trie`

You usually start from a list of words.

You can build a Trie from the list using the static constructor buildTrie:

const wordList: string[] = ...; // Your list of words 👈

const trie = Trie.buildTrie(wordList);

That's basically it! 💁🏼‍♂️

Now the Trie allows to search for any word (using searchTrie) and add any word (using addWord):

const hasWord = trie.searchTrie("sandro"); // Search word "sandro" in `trie`
trie.addWord("sandro"); // Add word "sandro" to `trie`

Note: This Trie implementation is mutable, you are allowed to modify the Trie (children, addWord, addChar) ☝️

What is a Trie?

When to use a Trie

How to use Trie

👋・Interested in learning more, every week?

What is a `Trie`?

When to use a `Trie`

How to use `Trie`