Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C++

Structure of a Trie

Explore the basic structure of a trie and understand how to build a TrieNode and Trie class in C++. Learn how each node represents an alphabet and how the isEndWord flag helps in word searches.

We'll cover the following...

Introduction

In this lesson, we will take a look at the basic structure of a trie and then build a class in C++ based on what we’ve studied.

g t t o o t->o h h t->h p p o->p u u h->u e e h->e s s u->s i i e->i r r i->r Root Root Root->t
Trie containing "top", "thus" and "their".

The Trie Node Class

The node of a trie represents an alphabet. For example, if we want to insert “hello” in the Trie, we will need to add 5 nodes, one for each alphabet. A typical node in a trie consists of three data members:

  • * children[]: An array which consists of pointers to children nodes. The size of this array depends on the number of alphabets. By default, all are set to NULL.
  • isEndWord: A flag to indicate the end of a word. It is set to false by default and is only updated when a word ends during insertion.

Here is the implementation in C++:

C++
#include <iostream>
using namespace std;
#define ALPHABET_SIZE 26
class TrieNode{
  public:
    TrieNode *children[ALPHABET_SIZE]; 
    bool isEndWord;
    TrieNode();
    void markAsLeaf();
    void unMarkAsLeaf();
};

The Trie Class

The Trie will be implemented using the TrieNode class. As discussed above, a Trie node represents one alphabet that keeps pointers to its children nodes. Each node can have at max 26 children if we are storing English words.

A root node is placed at the top and contains 26 pointers (one per alphabet). These pointers hold either NULL or another trieNode. The root is similar to the headNode from linked lists.

The index of the children pointers is decided based on the sequence of the alphabets (starting from 0). For instance, the node containing the alphabet a (if it exists) will be stored at the 0th index, b at the 1st, and node z will come at the 25th index.

All the words are stored in a top-bottom manner. While storing the last character, we should always set the isEndWord flag as true to indicate the end of a word. This technique helps us in searching for a word to see if it even exists.

A typical trie class looks like this in C++:

C++
#include <iostream>
using namespace std;
#define ALPHABET_SIZE 26
class TrieNode {
  public:
    TrieNode * children[ALPHABET_SIZE];
    bool isEndWord;
    TrieNode();
    void markAsLeaf();
    void unMarkAsLeaf();
};
class Trie {
  private:
    TrieNode * root;
  public:
    Trie();
    int getIndex(char t);
    void insertNode(string key);
    bool searchNode(string key);
    bool deleteNode(string key);
};