Trie Data Structure in Java

Sheeraz Gul Oct 12, 2023

Java Java Data Structure

Trie Data Structure in Java
Basic Operations of Trie Data Structure
Java Implementation of Trie Data Structure

This tutorial demonstrates the Trie data structure in Java.

Trie Data Structure in Java

Trie word is extracted from the word Retrieval, which is a sorted data structure used to store the set of strings. Trie can be defined as the data structure with the number of pointers equal to the number of characters in each node.

With the help of the word’s prefix, the Trie data structure can be used to search a word from a dictionary. In this scenario, if all the words in the dictionary are made from the 26 English alphabets, each Trie node will have 26 points.

The Trie data structure is also known as the Prefix tree or Digital tree, where the node’s position will determine the key with which the node will be connected. Let’s try to understand from the following figure how a Trie works:

Trie Data Structure Java

The above picture contains the tree structure for the words deal, delft, and delete.

Properties of Trie Data Structure

Here are the main properties for the Trie set of strings:

The Root node is always the null one.
Every child node will be sorted alphabetically.
Each node cannot have more than 26 children because of the English alphabet.
Every node can store one letter from the alphabet.

Application of Trie Data Structure

Let’s see some main applications for the Trie data structure:

The Trie can be used when there is a need to assume all the letters are lowercase.
When we have to only use the letter from a-z, with no hyphen, no punctuation, etc.
When the words have a limited length. For example, if we are working on a 2x2 board, the word length cannot be more than 4, so those words can be discarded.
Many words in the dictionary share the same stem, for example, lawn and lawnmower. The Trie can be used for these inflected words.

Basic Operations of Trie Data Structure

The Trie has three basic operations:

Insert Operation

The first operation is to insert a node into the Trie. To do that, we need to understand the following points:

Every letter of the input word will be inserted as an individual in a Trie node.
The character length will determine the length of the Trie.
The key character array will act as the children’s index.
If the current node has a reference to the current letter, set the current node that referenced the node. Otherwise, a new node should be created.

Search Operation

The second basic operation for Trie is searching a node. This operation is also similar to the insertion.

We only have to search a node using the same approach.

Delete Operation

The third operation is to delete a node. This is also an easy operation.

We have to consider two points before starting deletion:

If the node key is not found while searching, the delete operation will stop and exit.
If the node key is found while searching the Trie, the delete operation will delete the key.

Java Implementation of Trie Data Structure

Let’s try to implement the Trie data structure, which only supports lowercase a-z English characters. See example:

package delftstack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Trie_Node {
  // 26 characters for a – z
  private static final int CHARACTER_SIZE = 26;

  private boolean Is_Leaf;
  private List<Trie_Node> Trie_Children = null;

  // Constructor
  Trie_Node() {
    Is_Leaf = false;
    Trie_Children = new ArrayList<>(Collections.nCopies(CHARACTER_SIZE, null));
  }

  // function for insertion
  public void Insertion(String Node_Key) {
    System.out.println("Inserting the key \"" + Node_Key + "\"");

    // root node
    Trie_Node root_node = this;

    // repeat for every character of the key
    for (char character : Node_Key.toCharArray()) {
      // create a new Trie node if the path does not exist
      if (root_node.Trie_Children.get(character - 'a') == null) {
        root_node.Trie_Children.set(character - 'a', new Trie_Node());
      }

      // going to the next node
      root_node = root_node.Trie_Children.get(character - 'a');
    }

    // current node as a leaf
    root_node.Is_Leaf = true;
  }

  // Method for search
  public boolean Searching(String Node_Key) {
    System.out.print("Searching the key \"" + Node_Key + "\" : ");

    Trie_Node Current_Node = this;

    // repeat for the character of the key
    for (char character : Node_Key.toCharArray()) {
      // going to the next node
      Current_Node = Current_Node.Trie_Children.get(character - 'a');

      // reach out to the end of a path in the Trie if the string is invalid
      if (Current_Node == null) {
        return false;
      }
    }
    return Current_Node.Is_Leaf;
  }
}

public class Example {
  public static void main(String[] args) {
    // construct a new Trie node
    Trie_Node New_Trie = new Trie_Node();

    New_Trie.Insertion("delft");
    New_Trie.Insertion("delf");
    New_Trie.Insertion("del");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // false

    New_Trie.Insertion("delftstack");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // true
  }
}

The code above implements the insertion and searching operation of the Trie data structure. See the output:

Inserting the key "delft"
Inserting the key "delf"
Inserting the key "del"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : false
Inserting the key "delftstack"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : true

Now, the space complexity for the Trie data structure is O(N × M × C), where:

N - the number of strings
M - the maximum length of the strings.
C - the size of the alphabet

So the storage problem might occur in Java with the above space complexity.

We can also use the HashMap from Java to implement Trie to solve the storage problem. Let’s try to implement the Trie using HashMap:

package delftstack;

import java.util.HashMap;
import java.util.Map;

class Trie_Node {
  private boolean Is_Leaf;
  private Map<Character, Trie_Node> Trie_Children;

  // Constructor
  Trie_Node() {
    Is_Leaf = false;
    Trie_Children = new HashMap<>();
  }

  // Insertion
  public void Insertion(String Node_Key) {
    System.out.println("Inserting the key \"" + Node_Key + "\"");

    // root node
    Trie_Node root_node = this;

    for (char character : Node_Key.toCharArray()) {
      // if the path doesn't exist, create a new node.
      root_node.Trie_Children.putIfAbsent(character, new Trie_Node());

      // going to the next node
      root_node = root_node.Trie_Children.get(character);
    }
    root_node.Is_Leaf = true;
  }
  // Searching
  public boolean Searching(String Node_key) {
    System.out.print("Searching the key \"" + Node_key + "\" : ");

    Trie_Node Current_Node = this;

    // repeat
    for (char character : Node_key.toCharArray()) {
      // going to the next node
      Current_Node = Current_Node.Trie_Children.get(character);

      if (Current_Node == null) {
        return false;
      }
    }

    return Current_Node.Is_Leaf;
  }
}

public class Example {
  public static void main(String[] args) {
    // construct a new Trie node
    Trie_Node New_Trie = new Trie_Node();

    New_Trie.Insertion("delft");
    New_Trie.Insertion("delf");
    New_Trie.Insertion("del");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // false

    New_Trie.Insertion("delftstack");

    System.out.println(New_Trie.Searching("del")); // true
    System.out.println(New_Trie.Searching("delf")); // true
    System.out.println(New_Trie.Searching("delft")); // true
    System.out.println(New_Trie.Searching("delftstack")); // true
  }
}

The code does the same work but in a more memory-efficient way. See the output for Trie in Java:

Inserting the key "delft"
Inserting the key "delf"
Inserting the key "del"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : false
Inserting the key "delftstack"
Searching the key "del" : true
Searching the key "delf" : true
Searching the key "delft" : true
Searching the key "delftstack" : true

Author: Sheeraz Gul

Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.

LinkedIn Facebook