Trie Datastructure

Trie datastructure is used to store collection of strings. If you have a search problem with thousands and thousands of strings then you can use trie datastructure to store the string and perform search very efficiently on it. It helps to bring down the search complexity to the length of keys whereas if you use a well balanced binary search tree, it will take O(m*log n)  where m is the maximum string length and n is the number of keys in the tree.

Its a good datastructure for storing the dictionary, used to do prefix based search and you can also use it to sort the strings lexographically another alternative for this is to use a hash table. But in a hash table you cannot do a prefix based search and a regular hash table takes more space than a trie.

Trie is a tree datastructure and its made up of collection of nodes. Every trie has two component a map where the key is the character and the value is a trieNode which is used to establish the parent child relationship. The below is the data structure for the trieNode.

TrieNode {
      Map<Character, TrieNode>  children
      boolean endOfWord //Whether the character is the end of word or not
}

How to create a trieNode?

Lets look at the method to build a trie data structure for the word "abc", abd

Step 1: To form the trie tree for the word abc

Iteration 1

Iteration 2

Iteration 3

Step 2: To for trie tree for the word abd

Iteration 1

Code to form the Trie Node.

class TrieNode {
    char c;
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    boolean isLeaf;

    public TrieNode() {}

    public TrieNode(char c){
        this.c = c;
    }
}

public class TrieChain {
    private TrieNode root;

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

    // Insert a string into the trie.
    public void insert(String word) {
        HashMap<Character, TrieNode> children = root.children;

        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);

            TrieNode t;
            if(children.containsKey(c)){
                    t = children.get(c);
            }else{
                t = new TrieNode(c);
                children.put(c, t);
            }

            children = t.children;

            //set leaf node
            if(i==word.length()-1)
                t.isLeaf = true;  
        }
    }
}