Tries: Supporting a Variety of Data

Learn about the different types of tries through examples demonstrating the creation of tries for different sets of data.

We'll cover the following

We know that a trie is an N-aryIn an N-ary tree, a node can have a maximum of N children. This is in contrast to binary trees where a node can have at most two children. tree of characters, but that's a textual definition. A trie is not limited to strings and prefix search. Based on the use case, we can represent different data types as a trie and solve challenging problems using it.

We'll learn about the different types of tries constructed on different datasets through examples.

Trie of alphabet

We can represent strings as a trie of letters of alphabet or characters, which can be used to implement features like search-autocomplete or creating dictionaries.

For example, a trie of words ["app", "apple", "appeal", "apply", "ape"] would look like the figure below.

%0 node_1 A node_2 P node_1->node_2 node_1663140283512 P node_2->node_1663140283512 node_1663140346398 E node_2->node_1663140346398 node_1663140301496 E node_1663140283512->node_1663140301496 node_1663140360207 L node_1663140283512->node_1663140360207 node_1663140325871 A node_1663140301496->node_1663140325871 node_1663140365636 E node_1663140360207->node_1663140365636 node_1663140408567 Y node_1663140360207->node_1663140408567 node_1663140333916 L node_1663140325871->node_1663140333916
A trie of letters of alphabet

Trie of words

Sentences can be represented as a trie of words. The tries are used for pattern matching in text and finding frequently used words and phrases.

For example, a trie of sentences ["Ben has two books", "Ben has two games", "Ben has three bats"] would look like the figure below.

%0 node_1 Ben node_2 has node_1->node_2 node_1661875563953 two node_2->node_1661875563953 node_1661875577293 three node_2->node_1661875577293 node_1661875587498 books node_1661875563953->node_1661875587498 node_1661875593545 games node_1661875563953->node_1661875593545 node_1661875602131 bats node_1661875577293->node_1661875602131
A trie of words

Trie of bits

Binary numbers can be represented as a trie of bits. These tries can be used to perform range queries like finding the maximum XOR of binary digits in a list. 

For example, a trie of binary numbers ["10110", "11001", "10101"] would look like the figure below.

%0 node_1 1 node_2 1 node_1->node_2 node_3 0 node_1->node_3 node_1661875817584 0 node_2->node_1661875817584 node_1661875824607 1 node_3->node_1661875824607 node_1661875850834 0 node_1661875817584->node_1661875850834 node_1661875831142 1 node_1661875824607->node_1661875831142 node_1661875881270 0 node_1661875824607->node_1661875881270 node_1661875853657 1 node_1661875850834->node_1661875853657 node_1661875836173 0 node_1661875831142->node_1661875836173 node_1661875886289 1 node_1661875881270->node_1661875886289
A trie of bits

Trie of directory paths

Directory paths can be represented as a trie of folder and file names. These tries can be used to design a file system that allows us to create new paths, associate them with different values, and visualize the directory structure of a system.

For example, a trie of directory paths ["home/user/William/file1", "home/user/William/file2", "home/user/Ben/file1"] would look like the figure below.

%0 node_1 home node_2 user node_1->node_2 node_1661877237999 William node_2->node_1661877237999 node_1661877258103 Ben node_2->node_1661877258103 node_1661877266430 file1 node_1661877237999->node_1661877266430 node_1661877273380 file2 node_1661877237999->node_1661877273380 node_1661877279293 file1 node_1661877258103->node_1661877279293
A trie of directory paths (folders)