Search⌘ K
Home
Courses
Advanced Data Structures: Implementing Tries in C++ and Java

Tries: Supporting a Variety of Data

Explore how tries support a variety of data beyond strings. Understand their structure for alphabets, sentences, binary numbers, and directory paths. Learn to apply tries for tasks such as autocomplete, pattern matching, range queries, and file system design through examples.

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)