Problem Statement

A Trie (Prefix Tree) is a tree data structure used to efficiently store and search strings.

Implement a Trie with the following operations:

1. insert(String word) → Inserts a word into the trie.
2. search(String word) → Returns true if the word is in the trie.
3. startsWith(String prefix) → Returns true if there is any word in the trie that starts with the given prefix.

Example:

Input:
["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]

Output:
[null,null,true,false,true,null,true]

---

Approach to Solve the Problem (Simple Language)

Idea:

• A Trie is a tree of nodes where each node represents a character.
• Each node has:
  • An array/map of children nodes (for all possible next characters)
  • A boolean flag to mark the end of a word

Operations:

1. Insert:
   • Start from root
   • For each character in the word:
     • If the character node does not exist, create it
     • Move to the child node
   • Mark the last node as end of word
2. Search:
   • Start from root
   • Traverse each character of the word
     • If character node does not exist → return false
   • After last character, check isEndOfWord → return true if word exists
3. StartsWith:
   • Start from root
   • Traverse each character of the prefix
     • If character node does not exist → return false
   • If traversal succeeds → return true (prefix exists)

Why Trie works efficiently:

• Searching a word or prefix is O(L), where L = length of the word/prefix, independent of number of words.

---

Java Code Solution

class TrieNode {
    TrieNode[] children = new TrieNode[26]; // For lowercase letters a-z
    boolean isEndOfWord = false;
}

public class Trie {
    private final TrieNode root;

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

    // Insert a word into trie
    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    // Search for a word in trie
    public boolean search(String word) {
        TrieNode node = searchNode(word);
        return node != null && node.isEndOfWord;
    }

    // Check if any word starts with prefix
    public boolean startsWith(String prefix) {
        TrieNode node = searchNode(prefix);
        return node != null;
    }

    // Helper method to traverse trie for a word/prefix
    private TrieNode searchNode(String s) {
        TrieNode node = root;
        for (char ch : s.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) return null;
            node = node.children[index];
        }
        return node;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // true
        System.out.println(trie.search("app"));     // false
        System.out.println(trie.startsWith("app")); // true
        trie.insert("app");
        System.out.println(trie.search("app"));     // true
    }
}

---

Dry Run Example

Input:

Operations: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")

Step-by-step Execution:

1. insert(“apple”)
   • Traverse root → create nodes for ‘a’ → ‘p’ → ‘p’ → ‘l’ → ‘e’
   • Mark ‘e’ node as end of word
2. search(“apple”)
   • Traverse nodes: ‘a’ → ‘p’ → ‘p’ → ‘l’ → ‘e’
   • End node isEndOfWord = true → return true
3. search(“app”)
   • Traverse nodes: ‘a’ → ‘p’ → ‘p’
   • End node isEndOfWord = false → return false
4. startsWith(“app”)
   • Traverse nodes: ‘a’ → ‘p’ → ‘p’
   • Node exists → return true
5. insert(“app”)
   • Traverse nodes: ‘a’ → ‘p’ → ‘p’ (already exist)
   • Mark last ‘p’ as end of word
6. search(“app”)
   • Traverse nodes: ‘a’ → ‘p’ → ‘p’
   • isEndOfWord = true → return true

---

Textual Diagram for Understanding

Insert "apple":
root
 |
 'a'
  |
  'p'
   |
   'p'
    |
    'l'
     |
     'e' (endOfWord=true)

Insert "app":
'a'->'p'->'p' (mark 'p' as endOfWord=true)

Trie structure allows:
search("apple") → true
search("app") → true after inserting "app"
startsWith("app") → true

---

Complexity Analysis

• Time Complexity:
  • Insert: O(L)
  • Search: O(L)
  • StartsWith: O(L)
  • L = length of the word/prefix
• Space Complexity: O(N * L)
  • N = number of words, L = average length (each node can have up to 26 children)