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

#include <iostream>
#include <vector>
using namespace std;

vector<int> lexicalOrder(int num) {
  // your code goes here
  vector<int> result;
  return result;
}

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

// Definition of a trie node
class TrieNode
{
    public:
       	// A flag used to identify the last nodes of number (leaf nodes)
        bool isEndOfNum;
       	// children array store pointer to TrieNode of next 10 integer (0 to 9)
        TrieNode *children[10];
};

class Trie
{
    public:
        TrieNode * root;
        Trie()
        {
            root = new TrieNode();
        }
    
        void insert(int n)
        {
           	// convert num to string
            string digit = to_string(n);
    
           	//point current node to root
            TrieNode *curr = root;
    
           	//insert the stirng into trie
            for (auto &ch: digit)
            {
                if (curr->children[ch - '0'] == nullptr)
                {
                    curr->children[ch - '0'] = new TrieNode();
                }
    
                curr = curr->children[ch - '0'];
            }
    
           	// mark isEndOfNum true for 
           	// last node in the num string
            curr->isEndOfNum = true;
        }
    
       	// DFS to traverse the trie
        void dfs(TrieNode *root, vector<int> &result, string currStr)
        {
           	// return if root is null
            if (!root)
            {
                return;
            }
    
           	// if the current node
           	// is the last node of number
           	// add the number to result
            if (root->isEndOfNum)
            {
                result.push_back(stoi(currStr));
            }
    
           	// recrusively traverse the trie in preorder
            for (int i = 0; i < 10; ++i)
            {
                if (root->children[i])
                {
                    dfs(root->children[i], result, currStr + to_string(i));
                }
            }
        }
    
       	//  dfs to fetch all integers from trie
       	// in lexicographical order
        vector<int> getNums()
        {
            vector<int> ans;
            dfs(root, ans, "");
            return ans;
        }
};

// return the integers in lexical order
vector<int> lexicalOrder(int n)
{
   	// initilase a trie 

    Trie *trie = new Trie();

   	//insert all integers from 1 to num 
    for (int i = 1; i <= n; i++)
        trie->insert(i);

   	// use dfs to fetch all integers from trie
   	// in lexicographical order
    return trie->getNums();
}

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

class Solution {
   public static List<Integer> lexicalOrder(int num) {
        // your code goes here
        List<Integer> result = new ArrayList<>();
        return result;
    }
}

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

// Definition of a trie node
class TrieNode
{
   	// A flag used to identify the last nodes of number (leaf nodes)
    boolean isEndOfNum;
   	// children array store pointer to TrieNode of next 10 integer (0 to 9)
    TrieNode[] children = new TrieNode[10];
}

class Trie
{
    TrieNode root = new TrieNode();

    void insert(int n)
    {
       	// convert num to string
        String digit = Integer.toString(n);

       	//point current node to root
        TrieNode curr = root;

       	//insert the stirng into trie
        for (char c: digit.toCharArray())
        {
            int index = (int) c - '0';
            if (curr.children[index] == null)
            {
                curr.children[index] = new TrieNode();
            }

            curr = curr.children[index];
        }

       	// mark isEndOfNum true for 
       	// last node in the num string
        curr.isEndOfNum = true;
    }

   	// DFS to traverse the trie
    void dfs(TrieNode root, List<Integer> result, String currStr)
    {
       	// return if root is null
        if (root == null)
        {
            return;
        }

       	// if the current node
       	// is the last node of number
       	// add the number to result
        if (root.isEndOfNum)
        {
            result.add(Integer.parseInt(currStr));
        }

       	// recrusively traverse the trie in preorder
        for (int i = 0; i < 10; ++i)
        {
            if (root.children[i] != null)
            {
                dfs(root.children[i], result, currStr + Integer.toString(i));
            }
        }
    }

   	//  dfs to fetch all integers from trie
   	// in lexicographical order
    List<Integer> getNums()
    {
        List<Integer> ans = new ArrayList < > ();
        dfs(root, ans, "");
        return ans;
    }
}

class Solution
{
   	// return the integers in lexical order
    static List<Integer> lexicalOrder(int n)
    {
        System.out.println(n);
       	// initilase a trie 
        Trie trie = new Trie();

       	//insert all integers from 1 to num 
        for (int i = 1; i <= n; i++)
            trie.insert(i);

       	// use dfs to fetch all integers from trie
       	// in lexicographical order
        return trie.getNums();
    }
}

Java

Solve a medium-level problem of sorting numbers in range in lexicographical order using tries. 

Sorted Numbers

Solve a medium-level problem of sorting numbers in range in lexicographical order using tries.

Introduction to Tries

Prefix Search

Suffix Search

Bitwise Tries

Pattern Matching

File Systems

Trie Traversal

Search Engine

Miscellaneous

Conclusion

Sorted Numbers

Problem statement

Example 1

Example 2

Try it yourself

Intuition