Understanding Trie for DSA

A Trie, also known as a prefix tree, is a tree-like data structure used to store a collection of strings. Tries are particularly useful for tasks involving string searching, autocomplete, and spell-checking.

Key Characteristics

1. Structure: A Trie is organized like a tree, where each node represents a single character of a word. The root of the Trie represents an empty string.

2. Insertion: When you insert a word into a Trie, you start at the root and follow a path corresponding to the word's characters. If a node for a character doesn't exist, you create it. Once you've processed all characters of the word, you mark the last node as the end of a word.

3. Search: To search for a word in a Trie, you start at the root and follow the path of characters that match the word. If you can't find a node for a character or if the path doesn't end with a node marked as a word, the word is not in the Trie. The word is found if you reach the end of the word and the last node is marked as a word.

4. Efficiency: Tries are efficient because they allow you to quickly check if a word or a word's prefix exists in the collection. This is because you only need to traverse the path corresponding to the characters of the word or prefix.

Performance Considerations

1. Insertion: O(m), where m is the string's length.

2. Search: O(m), where m is the length of the string being searched.

3. Prefix Search: O(m + k), where m is the length of the prefix and k is the number of strings that share the prefix.

Implementation

public class Trie {
    // Inner class representing a node in the Trie
    private class Node {
        public boolean isWord; // Indicates if this node marks the end of a word
        public char value; // The character stored in this node
        public Node[] children; // Array of child nodes

        public Node(char c) {
            this.value = c;
            this.isWord = false;
            this.children = new Node[26]; // 26 slots for each letter of the alphabet
        }
    }

    private Node root; // Root of the Trie

    // Constructor to initialize the Trie
    public Trie() {
        root = new Node(' '); // Root node doesn't hold any character
    }

    // Method to insert a word into the Trie
    public void insert(String word) {
        Node current = root;
        for (char c : word.toCharArray()) {
            if (current.children[c - 'a'] == null) {
                current.children[c - 'a'] = new Node(c); // Create a new node if the character doesn't exist
            }
            current = current.children[c - 'a']; // Move to the next node
        }
        current.isWord = true; // Mark the last node as the end of a word
    }

    // Method to search for a word in the Trie
    public boolean search(String word) {
        Node current = root;
        for (char c : word.toCharArray()) {
            if (current.children[c - 'a'] == null) {
                return false; // If any character is not found, return false
            }
            current = current.children[c - 'a']; // Move to the next node
        }
        return current.isWord; // Check if the last node marks the end of a word
    }

    public static void main(String[] args) {
        Trie trie = new Trie();

        // Insert words into the Trie
        trie.insert("toy");
        trie.insert("tv");
        trie.insert("bye");
        trie.insert("bet");
        trie.insert("ben");

        // Search for words in the Trie
        System.out.println("Search 'toy': " + trie.search("toy")); // true
        System.out.println("Search 'tv': " + trie.search("tv")); // true
        System.out.println("Search 'by': " + trie.search("by")); // false
        System.out.println("Search 'bold': " + trie.search("bold")); // false
    }
}

Thank you for reading!

You can support me by buying me a book.