This course covers the intuition, implementation and problem-solving using tries.

edited - Advanced Data Structures - TRIES (1).png

Trie is an efficient tree-like data structure used to store and retrieve information. It is frequently tested in coding interviews, indicating its widespread use in solving many real-world software engineering challenges.

This course covers every aspect of the trie data structure, from the intuition of building a trie to coding it in famous programming languages for solving algorithmic problems and designing real-world systems. It assumes a prior knowledge of trees and basic data structures like lists and arrays. 

The problems in this course are categorized into various patterns, which will help you map new solutions to known issues using tries. The problems are of varying difficulties, from easy to hard, thus giving you an iterative learning experience. By the end of this course, you’ll be able to decode relevant trie problems, code their solutions in C++ and Java, and apply trie concepts to design complex software systems.

Advanced Data Structures: Implementing Tries in C++ and Java

words: ["i learn to code", "i love to code"]
K: 2

#include <iostream>
#include <vector>
using namespace std;

vector<string> topKFrequentWords(vector<string> words, int k) {
  // your code goes here
  vector<string> answer;
  return answer;
}


#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Definition of a trie node
class TrieNode
{
    public:
       	// children array store pointer to TrieNode of next 26 alphabets
        TrieNode *children[26];
       	// A parameter to store the complete word in the last node
        string word;
};

class Trie
{
    public:
        void addWord(TrieNode *root, string word)
        {
           	// point the current node 
           	// to the root
            TrieNode *curr = root;

           	// iterate through the letters of the word
            for (auto ch: word)
            {
                int index = ch - 'a';

               	// create a new node for letter
               	// if not already present
                if (curr->children[index] == nullptr)
                {
                    curr->children[index] = new TrieNode();
                }

                curr = curr->children[index];
            }

           	// store the complete word 
           	// in the last node 
            curr->word = word;
        }

    void getWord(TrieNode *curr, vector<string> &res, int k)
    {
        if (curr == nullptr)
            return;

       	// if last node is reached
       	// return the complete word
        if (curr->word != ""
            and res.size() < k)
        {
            res.push_back(curr->word);
        }

       	// if top K words are already in result
       	// return them
        if (res.size() == k)
            return;

       	// traverse the trie in pre order
       	// to get words in lexicographical order
        for (int i = 0; i < 26; i++)
        {
            if (curr->children[i] == nullptr)
                continue;
            getWord(curr->children[i], res, k);
        }
    }
};

vector<string> topKFrequentWords(vector<string> &sentences, int k)
{
    unordered_map<string, int> freqMap;

    string word;

   	// iterate through the sentences
    for (auto sentence: sentences)
    {
        for (int i = 0; i < sentence.size(); i++)
        {
           	// increment word count in hashmap
            if (sentence[i] == ' ')
            {
                freqMap[word]++;
                word = "";
            }
            else
                word += sentence[i];

            if (i == sentence.size() - 1)
            {
                freqMap[word]++;
                word = "";
            }
        }
    }

    int n = freqMap.size();

   	// create a vector for trienodes 
   	// to store roots for tries storing 
   	// words with different frequencies
    vector<TrieNode*> freqsTrieRoots;

   	// create root nodes 
    for (int i = 0; i <= n; i++)
    {
        TrieNode *newRootNode = new TrieNode();
        freqsTrieRoots.push_back(newRootNode);
    }

    Trie *trie = new Trie();
   	// based on the frequency
   	// add the word to the associated trie
    for (auto x: freqMap)
    {
        trie->addWord(freqsTrieRoots[x.second], x.first);
    }

   	// initialize a vector for result
    vector<string> result;

   	// traverse the trie storing the
   	// highest frequency words first
    for (int i = n; i >= 1; i--)
    {
        trie->getWord(freqsTrieRoots[i], result, k);
    }

    return result;
}

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
   public static List<String> topKFrequentWords(List<String> words, int k) {
        // your code goes here
        List<String> answer = new ArrayList<>();
        return answer;
    }
}


import java.util.*;
import java.lang.*;
import java.io.*;

// Definition of a trie node
class TrieNode
{
   	// children array store pointer to TrieNode of next 26 alphabets
    TrieNode[] children = new TrieNode[26];
   	// A parameter to store the complete word in the last node
    String word;
}

class Trie
{
    void addWord(TrieNode root, String word)
    {
       	// point the current node 
       	// to the root
        TrieNode curr = root;

       	// iterate through the letters of the word
        for (int i = 0; i < word.length(); i++)
        {
            char ch = word.charAt(i);
            int index = (int) ch - 'a';

           	// create a new node for letter
           	// if not already present

            if (curr.children[index] == null)
            {
                curr.children[index] = new TrieNode();
            }

            curr = curr.children[index];
        }

       	// store the complete word 
       	// in the last node
        curr.word = word;
    }

    void getWord(TrieNode curr, List<String> res, int k)
    {
       	// if last node is reached
       	// return the complete word

        if (curr == null)
            return;
        if (curr.word != null && res.size() < k)
        {
            res.add(curr.word);
        }

       	// if top K words are already in result
       	// return them

        if (res.size() == k)
            return;

       	// traverse the trie in pre order
       	// to get words in lexicographical order

        for (int i = 0; i < 26; i++)
        {
            if (curr.children[i] == null)
                continue;
            getWord(curr.children[i], res, k);
        }
    }
}

class Solution
{
    static List<String> topKFrequentWords(List<String> sentences, int k)
    {
        Map<String, Integer> freqMap = new HashMap();

       	// iterate through the sentences

        for (String sentence: sentences)
        {
            String[] words = sentence.split(" ");
            for (String word: words)
            {
               	// increment word count in hashmap
                freqMap.put(word, freqMap.getOrDefault(word, 0) + 1);
            }
        }

        int n = freqMap.size();

       	// create a vector for trienodes 
       	// to store roots for tries storing 
       	// words with different frequencies

        List<TrieNode> freqsTrieRoots = new ArrayList < > ();

       	// create root nodes 
        for (int i = 0; i <= n; i++)
        {
            TrieNode newNode = new TrieNode();
            freqsTrieRoots.add(newNode);
        }

        Trie trie = new Trie();

        for (String word: freqMap.keySet())
        {
            int frequency = freqMap.get(word);
            trie.addWord(freqsTrieRoots.get(frequency), word);
        }

       	// initialize a vector for result
        List<String> res = new ArrayList < > ();

       	// traverse the trie storing the
       	// highest frequency words first
        for (int i = n; i >= 1; i--)
        {
            trie.getWord(freqsTrieRoots.get(i), res, k);
        }

        return res;
    }
}

Java

// custom comparator for sorting
compare(pair a, pair b)
{
   	// a and b are pairs of format<int,string > to store frequency and word
   	// sort based on frequency
   	// first and then lexicographical order
    if (a.cnt is not equal to b.cnt)
        return a.cnt > b.cnt
    else
        return a.word < b.word
}

topKFrequent(sentences, k)
{
   	// create a hashmap
    mp = map(string, int)

   	// iterate through all sentences
    for every sentence in sentences
    {
       	//fetch the words in the sentences
        for every word in sentences
        {
            increment count
            for word in map mp
        }
    }

   	// create a list of pairs (int, string) to store frequency related data
    freqData = list(pair<int, string>)

   	// push map data into freqData list
    for (word, cnt) pair in mp
        freqData.add(new_pair{cnt, word})

   	// sort the freqData list using custom comparator 
    sort(freqData, compare)

    answer = list(string)

   	// pick the top K elements from the list
   	// add those to final answer
    for every(cnt, word) pair in frequencyData
    {
        if (k > 0)
        {
            answer.add(word)
            decrement k
        }
    }

    return answer
}

Solve a medium-level problem to find the K most frequent words in sentences. 

Frequent Words

Solve a medium-level problem to find the K most frequent words in sentences.

Frequent Words

Problem statement

Example

Try it yourself

Intuition

Sorting-based approach

Hashmap and priority queue-based approach