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

The Structure of a Trie

Explore the fundamental structure of a Trie, including TrieNode design and how to represent nodes as letters with child pointers. Understand how to build and implement a Trie class in Java for storing and searching words efficiently using the isEndWord flag.

We'll cover the following...

Introduction

Previously, we discussed a few properties that a Trie must hold in order to improve the performance. In this lesson, we will take a look at the basic structure of Trie and then build a class in Java with the help of these concepts.

Representation of a Node

A node in a Trie represents a letter in 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 two data members:

  • children[]: An array which consists of the children nodes. The size of this array depends on the number of alphabets (26 for the English language). By default, all elements 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 an end of the word is observed during insertion.

This is how we will code it in Java:

Java
class TrieNode
{
    TrieNode[] children;
    boolean isEndWord; //will be true if the node represents the end of word
    static final int ALPHABET_SIZE = 26; //Total # of English Alphabets = 26
    TrieNode(){
        this.isEndWord = false;
        this.children = new TrieNode[ALPHABET_SIZE]; 
    }
    //Function to mark the currentNode as Leaf
    public void markAsLeaf(){
        this.isEndWord = true;
    }
    //Function to unMark the currentNode as Leaf
    public void unMarkAsLeaf(){
        this.isEndWord = false;
    }
}

Implementation of the Trie Class

A Trie will be implemented using the TrieNode class. As discussed above, a TrieNode in Trie represents one letter which keeps its pointers on the children nodes. Each Node can have a max. of 26 children if we are storing English words.

A root TrieNode is placed at the top, which is Null, and contains 26 links (one per letter). These links are either Null or point to another TrieNode. The index of children pointers is decided based on the sequence of the letters (starting from 0). For instance, TrieNode A (if it exists) will be stored at the 0th index, B at the index 1, and TrieNode Z will come at the 25th index. For the next TrieNode, again, there could be 26 possibilities so we’ll initialize an array of 26 pointers.

All the words are stored in a top-bottom manner. While storing the last character, you should always set the isEndWord flag as true to indicate the end of a word, and store the particular value for the key(word). This technique helps us in searching for a word to see if it even exists. The size of a Trie depends on the number of letters each node can store and the number of words. A typical class of Trie looks like this in Java:

Java
class Trie{  
  private TrieNode root; //Root Node
  
  //Constructor
  Trie(){
    root = new TrieNode();
  }
  //Function to get the index of a character 't'
  public int getIndex(char t){
    return t - 'a';
  }
  
  //Function to insert a key,value pair in the Trie
  public void insert(String key,int value){}
  
  //Function to search given key in Trie
  public boolean search(String key){ return false;}
  
  //Function to delete given key from Trie
  public boolean delete(String key){ return false;}
}