What is a Trie?

This lesson gives a brief introduction to tries, their properties, and common applications.

We'll cover the following

Introduction

We are going to look at a tree-like data structure that proves to be very efficient while solving programming problems related to strings.

This data structure is called a trie and is also known as a Prefix Tree. We will soon find out why.

The word trie is derived from “retrieval”. As you can guess, the main purpose of using this structure is to provide fast retrieval. Tries are mostly used in dictionary word searches, search engine auto-suggestions, and IP routing.

Common Applications of Tries

Let’s have a look at some real-life examples to understand the role of tries.

Autocomplete Words

Today, the autocomplete feature is supported by almost all major applications. This feature can be efficiently implemented with the help of tries as they reduce the overall cost of performance.

Spell-Checking

Tries come in handy when you need to perform spell-check on a word entered by the user. This feature is helpful when the user does not know the exact spelling of a word they are searching for.

Searching for a Phone Contact

Another real-life use of tries is searching for contacts in our contact list. It provides auto-suggestions based on the combination of letters that we enter. As you’ll see later on, this can also be performed with hash tables, but a hash table won’t be as efficient as a trie.

Properties of a Trie

To maintain its overall efficiency, tries follow a certain structure:

  • Tries are similar to graphs as they are a combination of nodes where each node represents a unique alphabet.

  • Each node can point to null or other children nodes.

  • The size of a trie depends upon the number of alphabets. For example, in English, there are 26 letters so the number of unique nodes cannot exceed 26.

  • The depth of a trie depends on the longest word that it stores.

  • Another important property of a trie is that it provides the same path for words that share a common prefix. For example, “there” and “their” have a common prefix “the”. Hence, they will share the same path until “e”. After that, the path will split into two branches. This is the backbone of the trie functionality.

These are some of the basic properties that every trie must hold.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.