Try the Trie Tree

Published in

Webtips

4 min readMay 31, 2020

Ever wonder how applications can autocomplete words so fast? Trie is a type of tree data structure most commonly used for rapid search and word autocompletion. Using TypeScript, let’s build a simple Trie with a set of words and then have it autocomplete those words given partial strings.

The Node

Like any tree, let’s establish the structure of a single Node, without any of the helper methods.

// TrieNode.tsclass TrieNode {
  isCompleteWord: boolean;
  children: Map<string, TrieNode>;  constructor() {
    this.isCompleteWord = false;
    this.children = new Map<string, TrieNode>();
  }
}

You’ll notice we only have two attributes, isCompleteWord to keep track of what nodes represent the end of a word, and children as a Map of each letter corresponding to it’sTrieNode .

Trie Functionality

Now that we understand how a single node is constructed, we can talk about how the Trie works. Like all tree data structures, the Trie is just nodes connected to other nodes. that being said, with a Trie, all the nodes represent a single letter. While these letters don’t mean too much on their own, when you start from the root and chain them together, we quickly find ourselves making complete words.

Example:

    ROOT_NODE
       /
      T
     /
    R - E
   / \   \
  I   Y*  E*
 /
E*

Not including the root node, we have a total of 7 nodes and 3 words, each node representing a letter.

Building The Trie

We need to fill our tree with words, let’s add that functionality now. You may notice some TrieNode methods that we have not yet added, we will be doing that shortly.

// Trie.tsclass Trie {
  root: TrieNode
  
  constructor() {
    this.root = new TrieNode()
  }
  
  addWord(word: string): void {
    let trieNode: TrieNode = this.root;
    
    for (const letter of word) {
      if (trieNode.has(letter)) {
        trieNode = trieNode.get(letter);
      } else {
        trieNode = trieNode.setLetter(letter);
      }
    }    // last TrieNode is the end of a word
    trieNode.isCompleteWord = true
  }
}

Adding a word is relatively straightforward, we start with the root, and for each letter in the word we either get the corresponding node or setLetter. When we are done looping over each letter, the last TrieNode will have its isCompleteWord set to true.

Node Methods

Let’s add in those node helper methods we saw above. has will be checking to see if a node with the given letter exists in our children map. setLetter will make a child node with the given letter, and get will return the node with the given letter.

// TrieNode.tsclass TrieNode {
  isCompleteWord: boolean;
  children: Map<string, TrieNode>;  constructor() {
    this.isCompleteWord = false;
    this.children = new Map<string, TrieNode>();
  }  has(letter: string): boolean {
    return this.children.has(letter);
  }
  
  setLetter(letter: string): TrieNode {
    const trieNode = new TrieNode();
    this.children.set(letter, trieNode);
    return trieNode;
  }  get(letter: string): TrieNode {
    return this.children.get(letter);
  }
}

Great, now we can add words to our tree!

// index.tsconst trie = new Trie()trie.addWord("trie")
trie.addWord("try")
trie.addWord("tree")$ tsc index.ts --lib es5,es6,dom --target es5 && node index.js

Awesome, we are making some progress, but we aren’t quite there yet, we want our Trie to autocomplete!

Finding Words

To do this, we will be adding the method find to our Trie class. After that we can add findWords, our only recursive method, you can’t have a tree without recursion!

// Trie.tsclass Trie {
  ...
  find(letters: string): string[] {
    let trieNode: TrieNode = this.root;
    for (const letter of letters) {
      trieNode = trieNode.get(letter);
      if (!trieNode) {
        return []
      }
    }
    return trieNode.findWords(letters, [])
  }
}

First we build a chain of nodes starting from the root, matching our letters exactly, or returning an empty array. Once we have this base chain of letter nodes, its time we add findWords to TrieNode

// TrieNode.tsclass TrieNode {
  ...
  findWords(letters: string, results: string[]): string[] {
    this.children.forEach((trieNode, letter) => {
      const word = letters + letter;
      if (trieNode.isCompleteWord) {
        results.push(word);
      }
      trieNode.findWords(word, results);
    })
    return results;
  }
}

Given the base letters we are looking to autocomplete and an empty array, findWords is able to recursively check each node. When we find a node with isCompleteWord set to true, we push the chain of letters in to the results array to create a word. The results array is passed by reference, allowing us to keep pushing new words on to the original array.

Autocomplete

// index.tsconst trie = new Trie()trie.addWord("trie")
trie.addWord("try")
trie.addWord("tree")trie.find("tr") // ["trie", "try", "tree"]
trie.find("tre") // ["tree"]$ tsc index.ts --lib es5,es6,dom --target es5 && node index.js

There you have it, autocomplete in TypeScript using a Trie tree structure. The next step could be trying to autocomplete miss spelled words. I hope you enjoyed this example, and are inspired to start creating your own Trie trees.