A Trie (also known as digital tree) is an ordered tree structure used commonly for storing strings. Its name comes from the fact that Trie is reTrieval data structure. Its performance is better than a binary tree.

Except for the root of the Trie, every node of a Trie contains a single character (for example, for the word hey, there will be three nodes). Mainly, each node of a Trie contains the following:

• A value (a character, or a digit)
• Pointers to children nodes
• A flag that is true if the current node completes a word
• A single root used for branching nodes

The following diagram represents the sequence of steps for building a Trie containing the words cat, caret, and bye:

So, in code lines, a Trie node can be shaped as follows:

public class Node {

  private final Map<Character, Node> children = new HashMap<>();
  private boolean word;

  Map<Character, Node> getChildren() {
    return children;
  }

  public boolean isWord() {
    return word;
  }

  public void setWord(boolean word) {
    this.word = word;
  }
}

Based on this class, we can define a Trie basic structure as follows:

class Trie {

  private final Node root;

  public Trie() {
    root = new Node();
  }

  public void insert(String word) {
    ...
  }

  public boolean contains(String word) {
    ...
  }

  public boolean delete(String word) {
    ...
  }
}