Trie: Introduction

Let’s go over the Trie pattern, its real-world applications, and some problems we can solve with it.

Overview

Trie is a tree data structure used for storing and locating keys from a set. The keys are usually strings that are stored character by character—each node of a trie corresponds to a single character rather than the entire key.

The order of characters in a string is represented by edges between the adjacent nodes. For example, in the string “are”, there will be an edge from node aa to node rr to node ee. That is, node aa will be the parent of node rr, and node rr will be the parent of node ee.

The following illustration can help you understand how the strings are stored:

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