Trie Tree with JavaScript

Motivation

For the use case of searching strings, the time complexity of a binary search tree could be O(n) in the worst case. Where ‘n’ is the total number of strings stored in the binary tree. Therefore a better performing data structure is needed for searching strings in optimal time. The trie data structure avoids traversing the whole tree while searching for a string. A string containing only letters limits a trie node’s children to 26. This allows the search time complexity of a string to be O(s) where ‘s’ is the length of the string. So a trie tree is much more efficient in searching strings compared to the binary search tree.

Approach

The structure for a single node in the trie tree consists of an array of size 26 and a boolean to identify if it is the leaf node. Additionally, the leaf node can have an integer value or any other type of value mapped to the string. Each index in the array represents letters from a to z and each index can have a ‘TrieNode’ instance.

This image represents the root node in a trie tree.

Implementation

The implementation consists two classes one for the trie node and another one for the trie tree. The language of implementation is JavaScript with ES6 spec.

The properties for ‘TrieNode’ class are ‘value’, ‘isEnd’ and ‘arr’. The ‘arr’ variable is an array of size 26 filled with null values.

class TrieNode {
    constructor() {
        this.value = undefined;
        this.isEnd = false;
        this.arr = new Array(26).fill(null);
    }
}

The ‘TrieTree’ class has ‘insert’, ‘searchNode’, ‘startsWith’, ‘printString’ and ‘getRoot’ methods. Where the ‘insert’ method takes in a string and value as arguments. A prefix search can be performed with the ‘startsWith’ method.

class TrieTree {

    constructor() {
        this.root = new TrieNode();
    }

    insert(word, value) {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            const index = parseInt(word[i], 36) - 10;

            if (node.arr[index] === null) {
                const temp = new TrieNode();
                node.arr[index] = temp;
                node = temp;
            } else {
                node = node.arr[index];
            }
        }
        node.isEnd = true;
        node.value = value;
    }

    getRoot() {
        return this.root;
    }

    startsWith(prefix) {
        const node = this.searchNode(prefix);
        if (node == null) {
            return false;
        } else {
            this.printStrings(node, "");
            return true;
        }
    }

    printStrings(node, prefix) {
        if (node.isEnd) console.log(prefix);
        for (let i = 0; i < node.arr.length; i++) {
            if (node.arr[i] !== null) {
                const character = String.fromCharCode('a'.charCodeAt() + i);
                this.printStrings(node.arr[i], prefix + "" + (character));
            }
        }
    }

    searchNode(str) {
        let node = this.root;
        for (let i = 0; i < str.length; i++) {
            const index = parseInt(str[i], 36) - 10;
            if (node.arr[index] !== null) {
                node = node.arr[index];
            } else {
                return null;
            }
        }

        if (node === this.root)
            return null;

        return node;
    }
}

The code below shows how ‘TrieTree’ class can be instantiated and demonstrates the usage of various methods.

const trieTree = new TrieTree();
trieTree.insert("asdfasdf", 5);
trieTree.insert("cdfasdfas", 23);
trieTree.insert("cdfzsvljsdf", 42);

let answer = trieTree.searchNode("asdfasdf");
console.log(answer.value); //5
answer = trieTree.startsWith("cdf");
console.log(answer);
//asdfas
//zsvljsdf
//true

The time and space complexities for different methods are as follows:

• searchNode: Time: O(s), 's' is the string length, Space: O(1), as no extra data structures like queue or stack are used.
• insert: Time: O(s), 's' is the string length, Space: O(ns), where 'n' is the number of keys in the trie tree and 's' is the string length.
• startsWith: Time: O(s + k), 's' is the string length and 'k' is the largest length of the remaining matched string, Space: O(k), where 'k' is the largest length of the remaining matched string.

Applications

In front-end development trie trees have applications in the following domains:

• Autocomplete and type ahead functionalities.
• Spell checking.
• Searching.
• Sorting.

Additionally, a trie tree can help to store people’s phone numbers, IP addresses, and objects.

💡 Practice Coding

Practice coding questions that involve the trie tree and other data structures from top companies like Google, Amazon, Apple, and others. Signup today at Softnami's daily coding.