How to Implement a Trie Data Structure in Programming?

Question

How do you implement a Trie data structure effectively in a programming language?

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node = node.children.get(c);
            if (node == null) {
                return false;
            }
        }
        return node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) {
                return false;
            }
        }
        return true;
    }
}

Answer

A Trie, also known as a prefix tree, is a special type of tree used to store dynamic sets or associative arrays where the keys are usually strings. It offers efficient retrieval and storage of strings by utilizing the characters of the strings as paths down the tree.

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node = node.children.get(c);
            if (node == null) {
                return false;
            }
        }
        return node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) {
                return false;
            }
        }
        return true;
    }
}

Causes

Understanding the basic concept and structure of a Trie data structure.
Recognizing the advantages of using a Trie for efficient string searching and auto-completion.

Solutions

Define a TrieNode class that holds a map of character to TrieNode instances and a boolean indicating the end of a word.
Create a Trie class that contains methods to insert words, search for complete words, and check for prefixes using the defined TrieNode class.

Common Mistakes

Mistake: Not properly handling the insertion of duplicate words.

Solution: Ensure that the insertion function updates the existing nodes and marks the end of the word correctly.

Mistake: Ignoring the case sensitivity of characters during insertion and searching.

Solution: Convert all characters to a consistent case (e.g., lowercase) before processing them.

Mistake: Not implementing the startWith function to check word prefixes effectively.

Solution: Implement the startsWith method as a separate function to validate prefixes in the Trie.

Helpers

Trie implementation
Trie data structure
how to implement Trie
Trie example
prefix tree implementation