Understanding Trie Data Structure

Trie, also known as a prefix tree, is a tree-like data structure that proves very efficient for solving problems related to strings. If you’re dealing with scenarios where you have to search for strings, a Trie can be faster than hashing and BSTs.

What is a Trie?

A Trie is a special type of tree used to store associative data structures. Storing strings in a Trie allows us to quickly find words, retrieve them, and prefix them. Each node of the Trie consists of multiple branches, each representing a possible character of keys. We mark the last node of every key as the end of the word node.

Implementing a Trie in Java

Let’s start by creating a TrieNode class:

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;
    
    TrieNode(){
        isEndOfWord = false;
        for (int i = 0; i < 26; i++)
            children[i] = null;
    }
};

In this class, children is an array storing all child nodes that can be accessed using characters ‘a’-‘z’. isEndOfWord is a boolean field and is true if the node represents the end of a word.

Insertion in Trie

To insert a key into the Trie, we insert one character at a time. We start from the root, and for every character in the key, we check if it already exists in the Trie. If it does, we move to the next character. If it doesn’t, we add a new node. Finally, we mark the last character as the end of the word.

void insert(TrieNode root, String key) {
    TrieNode pCrawl = root;
    for (int level = 0; level < key.length(); level++) {
        int index = key.charAt(level) - 'a';
        if (pCrawl.children[index] == null)
            pCrawl.children[index] = new TrieNode();
        pCrawl = pCrawl.children[index];
    }
    pCrawl.isEndOfWord = true;
}

Searching in Trie

To search a key in the Trie, we start from the root and for every character in the key, we check if it exists in the Trie. If it does, we move to the next character. If it doesn’t, we return false. If we reach the end of the key, we check if isEndOfWord is true. If it is, we return true, else we return false.

boolean search(TrieNode root, String key) {
    TrieNode pCrawl = root;
    for (int level = 0; level < key.length(); level++) {
        int index = key.charAt(level) - 'a';
        if (pCrawl.children[index] == null)
            return false;
        pCrawl = pCrawl.children[index];
    }
    return (pCrawl != null && pCrawl.isEndOfWord);
}

Time and Space Complexities

The time complexity for creating a Trie is O(WL), where W is the number of words, and L is an average length of the word. This is because, for each word, we are traversing down the path that corresponds to each character in the word, so in total, the runtime comes out to be O(WL).

In terms of space complexity, since we are storing all the W words of average length L in the Trie, the space complexity also comes out to be O(W*L).

Conclusion

Tries are fascinating data structures that power some of the most fundamental software systems we use today, including search engines and databases. They offer a unique combination of efficiency and simplicity, making them a favorite among many computer scientists and engineers. So, the next time you’re faced with a problem involving strings, consider using a Trie! It might just be the perfect tool for the job.

Happy coding!