Tries In Typescript

Trie.test.ts

import { Trie, TrieNode } from './trie';

import { assert } from 'chai';

describe('Trie', () => {
  describe('with a single word', () => {
    let trie: Trie;
    beforeEach(() => {
      trie = new Trie();
      trie.insertWord('hey');
    });

    it('should properly detect words that are contained', () => {
      assert(trie.contains('hey'), 'Expected the trie to contain `hey`!');
    });

    it('should properly detect words that are not contained', () => {
      assert(
        !trie.contains('hello'),
        'Expected the trie to not contain `hello`!'
      );
      assert(!trie.contains('he'), 'Expected the trie to not contain `he`!');
      assert(!trie.contains('hi'), 'Expected the trie to not contain `hi`!');
      assert(
        !trie.contains('heya'),
        'Expected the trie to not contain `heya`!'
      );
    });
  });
});

Trie.ts

import { TrieNode } from "./TrieNode";

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;
  }
}

TrieNode.ts

type childrenType = {
  [key: string]: TrieNode;
};

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

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