Implementing trie in typescript

Trie is a typeof k-ary search tree used for storing and searching a specific key from a set.

Trie helps us to find the key in O(length of the key) time.

Check out the code example: Github: Trie implementation link

The trie will be made of trie nodes, which will have three fields. Key, children and isWord

key will store the character.
children will be the map that will keep track of the child trie node on the basis of a key character.
isWord will be a boolean field. which will mark if the node is the word or not.

Structure of the Trie Node:

// TrieNode.ts

type childrenType = {
  [key: string]: any
}

export class TrieNode {
  key: string | null;
  children: chilrenType;
  isWord: boolean;

  constructor(key: string | null) {
    this.key = key;
    this.children = {};
    this.isWord = false;
  }
}

Structure of the Trie :

Root Node

The Trie is made up of Trie Node
The root TrieNode will have the key value of null and every Trie Node will have two properties of children: an empty object and isWord as a false boolean field.
In Trie constructor, pass the value of null while instantiating the TrieNode for the root node.

// Trie.ts
import { TrieNode } from "./TrieNode";

export class Trie {
  root: TrieNode;
  constructor() {
    this.root = new TrieNode(null);
  }
...
}

Inserting word in Trie

The insertWord function will be responsible for inserting the word in the trie.

// Trie.ts
...
 insertWord(word: string) {
    let node = this.root;
    const n = word.length;

    for (let i = 0; i < n; i++) {
      const char = word[i];

      // set children
      if (!node.children[char]) {
        node.children[char] = new TrieNode(char);
      }

      // move node forward
      node = node.children[char];

      // set last char as word
      if (i === n - 1) {
        node.isWord = true;
      }
    }
  }

...

The insertWord function adds the word, character by character, in the trie. If the node with the key is not found in the trie at the particular position, then we create the new trie node. In the end, when we reach the last character, we mark that node, isWord field as true.

Searching in Trie

The contains function is responsible for checking if the word exists the trie. It will search for the word which we want to check.

// Trie.ts
...
contains(word: string): boolean {
    let node = this.root;
    let n = word.length;

    for (let i = 0; i < n; i++) {
      const char = word.charAt(i);

      if (node.children[char]) {
        node = node.children[char];
      } else {
        return false;
      }
    }

    return node.isWord;
  }
...

Final Code :

type childrenType = {
  [key: string]: any
}

export class TrieNode {
  key: string | null;
  children: chilrenType;
  isWord: boolean;

  constructor(key: string | null) {
    this.key = key;
    this.children = {};
    this.isWord = false;
  }
}

export class Trie {
  root: TrieNode;

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

  insertWord(word: string) {
    let node = this.root;
    const n = word.length;

    for (let i = 0; i < n; i++) {
      const char = word[i];

      // set children
      if (!node.children[char]) {
        node.children[char] = new TrieNode(char);
      }

      // move node forward
      node = node.children[char];

      // set last char as word
      if (i === n - 1) {
        node.isWord = true;
      }
    }
  }

  contains(word: string): boolean {
    let node = this.root;
    let n = word.length;

    for (let i = 0; i < n; i++) {
      const char = word.charAt(i);

      if (node.children[char]) {
        node = node.children[char];
      } else {
        return false;
      }
    }

    return node.isWord;
  }
}

Check out the code example: Github: Trie implementation link

Trie: K-ary search tree

Comments

More from this blog

Write-Ahead Log Explained: Build Crash-Safe Durability in 30 Lines

Connection Pooling Explained: Build One From Scratch in 30 Lines

Building PostgreSQL Extensions with Rust: A Complete Guide Using pgrx

I Tried Corrode’s “Prototyping in Rust” — And It Changed How I Build Things

My Research Journey into Rust & Performance: Solving the 1BRC Challenge ⚡️

Structure of the Trie Node:

Structure of the Trie :

Root Node

Inserting word in Trie

Searching in Trie

Final Code :

Command Palette

Comments

More from this blog

Structure of the Trie Node:

Structure of the Trie :

Root Node

Inserting word in Trie

Searching in Trie

Final Code :