What, Why How to implement Trie?

Why Trie Data Structure?

Whenever you start typing in modern applications - whether it's a search bar, messaging app, or navigation system, there's likely a Trie data structure working behind the scenes to efficiently match your input with potential suggestions or completions. The Trie's structure makes it particularly efficient for this kind of prefix-based searching and matching.

It is safe to say, that anytime you type something in any of the modern application, it might use trie to find the particular functionality you are looking for.

Anything you search on google is also an example of trie data structure. Trie data structure are used primarily for:

1. Autocomplete suggestion as you type
2. Spell Check/ Correction
3. Search History Recommendations

In Modern applications, it is used for:

1. Phone contact search
2. Dictionary lookup systems.
3. Social media hashtag suggestions.
4. Email address autocomplete.

A Trie efficiently handles prefix-based searching in Unisala. Enabling fast autocomplete suggestions as users type. This minimizes storage space compared to storing full strings.

Unisala topic search supports university names, majors, and spaces names, around 10000 names are broken down into tree structure. When publishing an article in unisala, you can choose from thousands and thousands of topic. Even when i publish this article, i can choose any topic i want to publish this post under.

if i type "data", then i am suggested words that matches my search. This is an application of Trie Data structure.

What is Trie Data Structure?

A Trie is a specialised tree used in searching most often with text. In most cases, it can out perform binary search tree, hash table and other ds.

Trie allow us to know if a word or part of word exist in the body of text.

Trie has usaully empty root node and from there letters are added. It's not binary tree, and can have multiple childrens.

When we search some like "A", if we have this in our tree, we know right away there are two words associated with "A" i.e ARE, AS.

Another name for trie is prefix tree. It's tree like data structure which proves to be quite efficient in solving these problems specific to strings.

Time Complexity:

Big of Trie = O(length of word), looking for a word ARE

• Look for A
• Look for R
• Look for E

Space Complexity:

Has a major advantage, we don't have to store word multiple times

An example of Trie:

{
  keys: {
    "d": {
      keys: {
        "a": {
          keys: {
            "y": {
              keys: {},
              isEnd: true
            }
          },
          isEnd: false
        }
      },
      isEnd: false
    },
    "b": {
      keys: {
        "a": {
          keys: {
            "y": {
              keys: {},
              isEnd: true
            }
          },
          isEnd: false
        }
      },
      isEnd: false
    }
  },
  isEnd: false
}

Coding for Trie Data Structure:

class Trie{
    constructor(){
        this.root = {
            keys:{},
            isEnd: false
        }
    }

insert(word, node = this.root){
 if(word.length === 0){
   node.isEnd = true
   return
  }

 if(!node.keys[word[0]]){
   node.keys[word[0]] = {
       keys:{},
       isEnd: false
   }
 }
 this.insert(word.substring(1), node.keys[word[0]])
}

search(word, node = this.root){
  if(word.length === 0){
     return node.isEnd
  }
  if(!node.keys[word[0]]){
     return false
  }
  return this.search(word.substring(1), node.keys[word[0]])
 }

startsWith(prefix, node = this.root) {

 if(prefix.length === 0){
  return true
 }
 if(!node.keys[prefix[0]]){
   return false
 }
return this.startsWith(
        prefix.substring(1), 
        node.keys[prefix[0]]
       )
}

This is basic algorithm of Trie data structure.

Design Add and Search Word Data Structure

Design a data structure that supports adding new words and searching for existing words.

Implement the WordDictionary class:

• void addWord(word) Adds word to the data structure.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example 1:

Input:
["WordDictionary", "addWord", "day", "addWord", "bay", "addWord", "may", "search", "say", "search", "day", "search", ".ay", "search", "b.."]

Output:
[null, null, null, null, false, true, true, true]

Explanation:
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("day");
wordDictionary.addWord("bay");
wordDictionary.addWord("may");
wordDictionary.search("say"); // return false
wordDictionary.search("day"); // return true
wordDictionary.search(".ay"); // return true
wordDictionary.search("b.."); // return true

Insert is the same as previous code, however this time, we need to adjust our search to match "." as wildcard, where if we encounter one of these, we check for all our children in the current node

search(word, node = this.root){
  if(word.length === 0){
     return node.isEnd
  }
  if(word[0] ==="."){
    return Object.values(node.keys).some( child => {
        return this.word(word.substring(1), child)
    })
  }

  if(!node.keys[word[0]]){
     return false
  }
  return this.search(word.substring(1), node.keys[word[0]])
 }

#trie #datastructure #trees