How to implement PhoneBook using tries data structure in typescript

Trie is a node-based data structure. It is used to implement word lookups. It is better than the use of HashTable because it can store efficiently sorted data and don’t have to use a sorting algorithm while retrieving data.

We’ll start by defining a trie that will hold phone book data and then develop an algorithm to search for a given name in the phone book

 In this section, we’ll see how Trie Data Structure can be used to implement phone book search using TypeScript.

By the end of this tutorial you will be get familiar with

• How to insert data in trie
• How to find prefix match in trie
• How to find all the prefix match in trie

In this section, we will implement phone book search using Trie DataStructure. First, you have to create nodes which represent letter in alphabet like nodeA,nodeB,nodeC etc. These nodes will be used as a base of the trie data structure.

—

class Contact {
  phone: string;
  name: string;
  constructor(name: string, phone: string) {
    this.phone = phone;
    this.name = name;
  }
}
class TrieNode {
  children: { [key: string]: TrieNode };
  isWord: boolean;
  contact: Contact;
  constructor() {
    this.children = {};
    this.isWord = false;
    this.contact = new Contact("", "");
  }
}

Now let’s create a Trie class

class Trie<T> {
  root: TrieNode;
  constructor() {
    this.root = new TrieNode();
  }
}

Now, we need to add children nodes which represent numbers like
node1A,node2B,node3C etc. These child nodes contain letters that come before them in alphabet order and also they point to their parents after them in alphabet order (i.e node1A points to nodeA). The process of adding these child nodes is done recursively until there is no left child or right child available for addition.

 insert(contact: Contact) {
    let node = this.root;
    for (let i = 0; i < contact.name.length; i++) {
      let c = contact.name[i];
      if (!node.children[c]) {
        node.children[c] = new TrieNode();
      }
      node = node.children[c];
    }
    node.isWord = true;
    node.contact = contact;
  }

Search Method

search(name: string) {
    let node = this.root;
    for (let i = 0; i < name.length; i++) {
      let c = name[i];
      if (!node.children[c]) {
        return null;
      }
      node = node.children[c];
    }
    if (node.isWord) {
      return node.contact;
    }
    return null;
  }

getContacts

 // get all contacts that start with the given prefix
  getContacts(prefix: string) {
    let node = this.root;
    for (let i = 0; i < prefix.length; i++) {
      let c = prefix[i];
      if (!node.children[c]) {
        return [];
      }
      node = node.children[c];
    }
    return this.getAllContactsInternal(node);
  }

  private getAllContactsInternal(node: TrieNode) {
    let contacts: Contact[] = [];
    if (node.isWord) {
      contacts.push(node.contact);
    }

    for (let child in node.children) {
      contacts = contacts.concat(
        this.getAllContactsInternal(node.children[child])
      );
    }
    return contacts;
  }

How to Use

Let’s use our trie data structure and test the output

let contacts = new Trie<Contact>();

//add contacts
contacts.insert(new Contact("John", "123456789"));
contacts.insert(new Contact("saohny", "987654321"));
contacts.insert(new Contact("Johnny", "123456789"));
contacts.insert(new Contact("Johnathan", "987654321"));
contacts.insert(new Contact("Johnathon", "123456789"));
contacts.insert(new Contact("santosh", "987654321"));
contacts.insert(new Contact("santosh kumar", "123456789"));

//search for contacts
console.log(contacts.getContacts("sa"));

As you can see in the above program I have added some dummy contacts. Now I am searching for all the contacts that starts with sa and you can see in the below that it returns all the name start with sa

Output

[ Contact { phone: '987654321', name: 'saohny' },
  Contact { phone: '987654321', name: 'santosh' },
  Contact { phone: '123456789', name: 'santosh kumar' } ]

Complete Code

class Contact {
  phone: string;
  name: string;
  constructor(name: string, phone: string) {
    this.phone = phone;
    this.name = name;
  }
}
class TrieNode {
  children: { [key: string]: TrieNode };
  isWord: boolean;
  contact: Contact;
  constructor() {
    this.children = {};
    this.isWord = false;
    this.contact = new Contact("", "");
  }
}

class Trie<T> {
  root: TrieNode;
  constructor() {
    this.root = new TrieNode();
  }
  insert(contact: Contact) {
    let node = this.root;
    for (let i = 0; i < contact.name.length; i++) {
      let c = contact.name[i];
      if (!node.children[c]) {
        node.children[c] = new TrieNode();
      }
      node = node.children[c];
    }
    node.isWord = true;
    node.contact = contact;
  }

  search(name: string) {
    let node = this.root;
    for (let i = 0; i < name.length; i++) {
      let c = name[i];
      if (!node.children[c]) {
        return null;
      }
      node = node.children[c];
    }
    if (node.isWord) {
      return node.contact;
    }
    return null;
  }
  // get all contacts that start with the given prefix
  getContacts(prefix: string) {
    let node = this.root;
    for (let i = 0; i < prefix.length; i++) {
      let c = prefix[i];
      if (!node.children[c]) {
        return [];
      }
      node = node.children[c];
    }
    return this.getAllContactsInternal(node);
  }

  private getAllContactsInternal(node: TrieNode) {
    let contacts: Contact[] = [];
    if (node.isWord) {
      contacts.push(node.contact);
    }

    for (let child in node.children) {
      contacts = contacts.concat(
        this.getAllContactsInternal(node.children[child])
      );
    }
    return contacts;
  }
}