Course4all

Implement Trie (Prefix Tree)

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trie.

Implement Trie (Prefix Tree)

Implement a trie which supports insert, search, and startsWith operations.
Medium

Examples

Input: ["Trie", "insert", "search", "search", "startsWith"] [[], ["apple"], ["apple"], ["app"], ["app"]]
Output: [null, null, true, false, true]
Approach 1

Level I: HashMap-based Trie

Intuition

Flexible implementation using a HashMap for children, suitable for any character set (Unicode).
⏱ O(L)💾 O(N * L)

Detailed Dry Run

Insert 'apple': R -> a -> p -> p -> l -> e (end).
java
import java.util.*;
class Trie {
    class Node { Map<Character, Node> children = new HashMap<>(); boolean isEnd = false; }
    Node root = new Node();
    public void insert(String w) { Node c=root; for(char x:w.toCharArray()) { c.children.putIfAbsent(x, new Node()); c=c.children.get(x); } c.isEnd=true; }
    public boolean search(String w) { Node n=find(w); return n!=null && n.isEnd; }
    public boolean startsWith(String p) { return find(p)!=null; }
    private Node find(String s) { Node c=root; for(char x:s.toCharArray()) { c=c.children.get(x); if(c==null) return null; } return c; }
}
Approach 2

Level III: Array-based Trie (Optimal)

Intuition

Static array [26] for lowercase English. Fastest possible access with minimal memory overhead for dense tries.
⏱ O(L)💾 O(N * L * 26)

Detailed Dry Run

Insert 'cat': root.children['c'-'a'] -> node1.children['a'-'a'] -> node2.children['t'-'a'] -> node3(isEnd=true).
java
class Trie {\n    class Node { Node[] children = new Node[26]; boolean isEnd = false; }\n    Node root = new Node();\n    public void insert(String w) { Node c=root; for(char x:w.toCharArray()) { int i=x-'a'; if(c.children[i]==null) c.children[i]=new Node(); c=c.children[i]; } c.isEnd=true; }\n    public boolean search(String w) { Node n=find(w); return n!=null && n.isEnd; }\n    public boolean startsWith(String p) { return find(p)!=null; }\n    private Node find(String s) { Node c=root; for(char x:s.toCharArray()) { int i=x-'a'; if(c.children[i]==null) return null; c=c.children[i]; } return c; }\n}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionExpression Add Operators
Next Question →Add and Search Word