Softnami
Author: Hussain Mir Ali

I am interested in web and mobile technologies.

If you any questions or feedback then message me at devtips@softnami.com.

Announcements
Ads

Call predictor: AI based call prediction

Download

2020

Feb
Jan

2019

Dec
Nov
Jul
May
Mar
Jan

2018

Nov
Sep
Jul
Jun
Apr
Feb
Jan

2017

Dec
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Jan

2016

Dec
Oct
Sep
Aug
Jul

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.

trie node

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:

Applications

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

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.