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: ["pay", "paid", "pat", "app", "apple", "apply", "ape"]
pref: "pa"

words: [“pay”, “paid”, “pat”, “app”, “apple”, “apply”, “ape”]
pref: "ap"

#include <iostream>
#include <vector>
using namespace std;

int prefixCount(vector<string>& words, string prefix) {
    // your code goes here
    return -1;
}

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

// Definition of TrieNode
class TrieNode
{
	public:
		// children array store pointer to TrieNode of next 26 alphabets
		TrieNode *children[26];
    	// An integer to identify the number of words beginning with
    	// the prefix starting from root node and ending on current node
    	int prefixCount = 0;
};

class Trie
{
	TrieNode * root;
	public:
		Trie()
		{
			//create the root of the trie
			root = new TrieNode();
		}

    	void insert(string word)
    	{
    		// set current pointer to the root node
    		TrieNode *curr = root;
    		for (char c: word)
    		{
    			c -= 'a';
    			//create a new node if not already exists
    			if (curr->children[c] == nullptr)
    			{
    				curr->children[c] = new TrieNode();
    			}
    
    			curr = curr->children[c];
    			// increment the value of prefix count for current trie node
    			curr->prefixCount++;
    		}
    	}
    
    	int countPrefixes(string word)
    	{
    		// set current pointer to the root node
    		TrieNode *curr = root;
    		for (char c: word)
    		{
    			c -= 'a';
    			// if an alphabet in the word is not found
    			// it implies prefix does not exist in the trie
    			// hence, return 0 as ans
    			if (curr->children[c] == nullptr)
    			{
    				return 0;
    			}
    
    			curr = curr->children[c];
    		}
    
    		// if the prefix was found in the trie
    		// return the value of prefixCount
    		// associated with the last trie node of the prefix
    		// which is the current Trie node.
    		return curr->prefixCount;
    	}
};

int prefixCount(vector<string> &words, string prefix)
{
	// Initialize a trie
	Trie *trie = new Trie();

	// insert all words in the trie
	for (string word: words)
		trie->insert(word);

	// count the number of words with the given prefix
	return trie->countPrefixes(prefix);
}

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

class Solution {
   public static int prefixCount(List<String> words, String pref) {
        // your code goes here
        return -1;
    }
}

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

// Definition of TrieNode
class TrieNode
{
	// children array store pointer to TrieNode of next 26 alphabets
	TrieNode[] children = new TrieNode[26];
	// An integer to identify the number of words beginning with
	// the prefix starting from root node and ending on current node
	int prefixCount = 0;
}

class Trie
{
	//create the root of the trie
	private TrieNode root = new TrieNode();

	public void insert(String word)
	{
		// set current pointer to the root node
		TrieNode curr = root;

		for (char c: word.toCharArray())
		{
			int index = (int) c - 'a';
			//create a new node if not already exists
			if (curr.children[index] == null)
				curr.children[index] = new TrieNode();
			curr = curr.children[index];
			// increment the value of prefix count for current trie node
			curr.prefixCount++;
		}
	}

	public int countPrefixes(String word)
	{
		// set current pointer to the root node
		TrieNode curr = root;

		// iterate through all characters of the given word
		for (char c: word.toCharArray())
		{
			int index = (int) c - 'a';
			// if a character in the word is not found, return false
			if (curr.children[index] == null)
			{
				return 0;
			}

			curr = curr.children[index];
		}

		// if the prefix was found in the trie
		// return the value of prefixCount
		// associated with the last trie node of the prefix
		// which is the current Trie node.
		return curr.prefixCount;
	}
}

class Solution
{
	public static int prefixCount(List<String> words, String prefix)
	{
		// Initialize a trie
		Trie trie = new Trie();

		// insert all words in the trie
		for (String word: words)
			trie.insert(word);

		// count the number of words with the given prefix
		int count = trie.countPrefixes(prefix);
		return count;
	}
}

Java


// returns the count of words in the list, which have pref as a prefix
int prefixCount(words, pref) 
{
    count = 0
    for every word in words list
        //check if pref is a prefix of word
        if isPrefix(pref, word) is true
            count+1
    return count
}

// checks if pref is a prefix of word 
boolean isPrefix(pref, word)
{
    for char at index i the pref and in the word
        if character at index in pref, equals to the character at index in word
            continue
        else 
            break 
        
    if the value of index equals the length of pref
        return true
}

Solve an easy problem of counting prefixes of strings using tries.

Prefix Count

Problem statement

Example 1

Example 2

Try it yourself

Intuition