Trie- k-ary search tree

hashnode blog link

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

Github: Trie implementation link

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