DEV Community

Dev Cookies
Dev Cookies

Posted on

🌲 Trie (Prefix Tree) Data Structure – Complete Guide with Java Code & LeetCode Questions

📌 Introduction

A Trie (pronounced "try") is a special tree-like data structure used to efficiently store and retrieve keys in a dataset of strings. It is especially useful for dictionary, autocomplete, and prefix search problems.

🧠 Why Use a Trie?

  • Fast lookup for words and prefixes.
  • Efficient storage for words with shared prefixes.
  • Great for autocomplete and spell-checking systems.

🔧 Trie Node Structure in Java

Each node contains:

  • A Map or array of children.
  • A boolean flag indicating if it's the end of a word. 
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;

    public TrieNode() {}
}
Enter fullscreen mode Exit fullscreen mode

🏗️ Trie Implementation in Java 

class Trie {
    private TrieNode root;

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

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

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

    // Search prefix
    public boolean startsWith(String prefix) {
        return searchNode(prefix) != null;
    }

    private TrieNode searchNode(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int idx = ch - 'a';
            if (node.children[idx] == null)
                return null;
            node = node.children[idx];
        }
        return node;
    }
}
Enter fullscreen mode Exit fullscreen mode

🧪 Example Usage 

public class Main {
    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
    }
}
Enter fullscreen mode Exit fullscreen mode

🧠 Trie vs HashMap vs BST

Feature Trie HashMap BST
Time Complexity O(L) O(1) avg O(log N)
Space Efficiency Medium-High Low Medium
Prefix Search ✅ Efficient ❌ Inefficient ❌ Inefficient
Use Case Dictionary, Autocomplete Key-Value Store Sorted Data

💡 Real-Life Use Cases

  • Autocomplete engines (Google search).
  • Spell-checkers.
  • IP routing (Longest Prefix Match).
  • Word games like Boggle or Scrabble.

🔥 Top LeetCode Problems on Trie

Problem Description Link
208. Implement Trie (Prefix Tree) Basic Trie operations 🔗 LeetCode
211. Design Add and Search Words Data Structure Supports wildcard search 🔗 LeetCode
212. Word Search II Search words in 2D grid using Trie + DFS 🔗 LeetCode
648. Replace Words Replace words in sentence using Trie dictionary 🔗 LeetCode
720. Longest Word in Dictionary Longest word built one char at a time 🔗 LeetCode
676. Implement Magic Dictionary Similar to word search with wildcard 🔗 LeetCode
1268. Search Suggestions System Auto-suggestions using Trie 🔗 LeetCode
745. Prefix and Suffix Search Complex prefix+suffix queries 🔗 LeetCode

⚙️ Time and Space Complexity

Operation Time Complexity Space Complexity
Insert O(L) O(26 × L × N)
Search O(L) O(1)
Prefix Match O(L) O(1)

L = length of the word, N = number of words

📚 Advanced Variants

  • Compressed Trie / Radix Tree – optimized for memory.
  • Ternary Search Tree – space-efficient Trie.
  • DAWG (Directed Acyclic Word Graph) – minimized form of Trie.

✍️ Final Thoughts

Trie is one of the most powerful data structures when dealing with words and prefixes. While it may consume more space than HashMaps or Sets, it provides unmatched efficiency in problems involving prefixes, auto-completion, and pattern matching.

Top comments (1)