Implement Trie

Intuition

A Trie is a prefix tree. Each node has up to 26 children (for lowercase letters) and an isEnd flag. Insert: walk/create nodes for each character. Search: walk nodes, return isEnd at the last node. StartsWith: walk nodes, return true if path exists.

Algorithm

1TrieNode: TrieNode[26] children; bool isEnd.
2Insert(word): for each char c, create child[c-"a"] if null. Mark isEnd at last node.
3Search(word): traverse nodes. Return isEnd at last node (false if path not found).
4StartsWith(prefix): traverse nodes. Return true if all nodes exist.

Example Walkthrough

Input: Insert "apple". Search "apple", "app".

1.Insert: aâ†’pâ†’pâ†’lâ†’e (isEnd=true). Search "apple": reach isEnd=true âœ“. Search "app": reach e node, isEnd=false â†’ false.

Output: true, false

Common Pitfalls

•isEnd marks a complete word â€” do not confuse with "has children" (which indicates a prefix).

Implement Trie.java

Java

// Approach: Trie node with 26 children and an isEnd flag. Insert, search, and startsWith via character traversal.
// Time: O(len) per op Space: O(total chars)
class Trie {

    Node root;

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

    // Insert a word into the Trie
    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {

            char ch = word.charAt(i);
            if (!node.isNode(ch))
                node.put(ch, new Node());

            node = node.get(ch);
        }
        node.setEnd();
    }

    // Search for a word in the Trie
    public boolean search(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {

            char ch = word.charAt(i);
            if (!node.isNode(ch))
                return false;

            node = node.get(ch);
        }
        return node.isEnd();
    }

    // Check if a prefix exists in the Trie
    public boolean isPrefix(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {

            char ch = word.charAt(i);
            if (!node.isNode(ch))
                return false;

            node = node.get(ch);
        }
        return true;
    }
}

class Node {
    Node nde[] = new Node[26];
    boolean end = false;

    Node get(char ch) {
        return nde[ch - 'a'];
    }

    boolean isNode(char ch) {
        return nde[ch - 'a'] != null;
    }

    void put(char ch, Node node) {
        nde[ch - 'a'] = node;
    }

    void setEnd() {
        end = true;
    }

    boolean isEnd() {
        return end;
    }
}

Was this solution helpful?