What is a Trie?

This lesson gives a brief introduction to Trie, its properties, and common applications.

Introduction

Till now, we only studied some of the commonly used Trees like Red-Black, 2-3 Trees, etc. In this chapter, we are going to look at a tree-like data structure which proves to be really efficient while solving programming problems related to Strings. This data structure is called Trie and is also known as “Prefix Trees”; we will find out why it’s named that later.

💡 Did you know?

Trie basically comes from the word “retrieval”, as the main purpose of using this structure is that it provides fast retrieval. Tries are mostly used for searching words in the dictionary, providing auto-suggestions in search engines, and for IP routing.

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