🌳 Understanding Trie (Prefix Tree) — From Fundamentals to LeetCode Problems

Harsh Jaiswal

7 min read

·

1 day ago

--

Listen

Share

Introduction

While learning Data Structures and Algorithms, I recently started revising Trie (Prefix Tree), a tree-based data structure mainly used for storing and searching strings efficiently.

Unlike arrays, linked lists, or binary search trees, Trie is specifically designed to handle strings and their prefixes.

For example, consider these words:

• apple
• app
• application
• apt
• bat

Instead of storing these words independently, Trie stores their characters in a tree structure, allowing words with common prefixes to share the same path.

This makes Trie particularly useful in applications such as:

• Autocomplete and search suggestions.
• Dictionary implementations.
• Prefix-based searching.
• Spell checking.
• Word searching.

Let’s understand how it works.

1. What is Trie?

A Trie (Prefix Tree) is a tree-based data structure in which each node represents a character, and the path from the root to a node represents a prefix or a complete word.

The important idea behind Trie is that words having common prefixes share the same nodes.

For example, consider:

apple, app, apt, bat

Their Trie representation looks like this:

                  Root
                 /    \
                a      b
                |      |
                p      a
               / \     |
              p   t    t
              |
              l
              |
              e

Here:

• apple and app share the prefix app.
• app and apt share the prefix ap.
• bat follows a separate path.
• Each word-ending node is marked using a boolean variable called isEnd.

Important: Reaching a node does not necessarily mean that a complete word exists. We need isEnd = true to identify a complete word.

2. Trie Node Structure

In a standard Trie implementation for lowercase English letters, each node contains:

1. children[26]: An array of pointers representing the 26 possible lowercase English characters.
2. isEnd: A boolean variable indicating whether a complete word ends at that node.

class Node {
public:
    Node* children[26];
    bool isEnd;

    Node() {
        for(int i = 0; i < 26; i++) {
            children[i] = NULL;
        }        isEnd = false;
    }
};

Why do we use children[26]?

We map every lowercase English character to an index:

int idx = ch - 'a';

For example:

• a → 0
• b → 1
• c → 2
• z → 25

This allows us to access the next character directly in O(1) time.

3. Important Trie Operations

There are three fundamental operations that we should understand.

A. Insert()

The insert operation adds a word into the Trie.

Approach:

1. Start from the root node.
2. Traverse every character of the word.
3. Calculate its index using ch - 'a'.
4. If the corresponding child does not exist, create a new node.
5. Move to that child.
6. After processing all characters, mark the current node as isEnd = true.

void insert(string word) {
    Node* curr = root;

    for(char ch : word) {
        int idx = ch - 'a';        if(curr->children[idx] == NULL) {
            curr->children[idx] = new Node();
        }        curr = curr->children[idx];
    }    curr->isEnd = true;
}

B. Search()

The search operation checks whether a complete word exists in the Trie.

Approach:

1. Start from the root.
2. Traverse each character.
3. If any required child does not exist, return false.
4. Otherwise, continue moving through the Trie.
5. After processing the complete word, check isEnd.

bool search(string word) {
    Node* curr = root;

    for(char ch : word) {
        int idx = ch - 'a';        if(curr->children[idx] == NULL) {
            return false;
        }        curr = curr->children[idx];
    }    return curr->isEnd;
}

Important: We check isEnd because a prefix can exist without being a complete word.

C. StartsWith()

This operation checks whether any word in the Trie starts with a given prefix.

Unlike search, it does not require the last node to have isEnd = true.

bool startsWith(string prefix) {
    Node* curr = root;

    for(char ch : prefix) {
        int idx = ch - 'a';        if(curr->children[idx] == NULL) {
            return false;
        }        curr = curr->children[idx];
    }    return true;
}

4. Time and Space Complexity

Let L represent the length of the given word or prefix.

OperationTime ComplexityInsertO(L)SearchO(L)StartsWithO(L)

Space Complexity: O(N × L) in the worst case, where N is the number of inserted words and L is their maximum length, assuming a fixed 26-character alphabet.

Trie is efficient for prefix-based operations because we only traverse the characters of the given string instead of checking every stored word.

5. LeetCode Problems I Solved

After understanding the basic Trie implementation, I applied the concept to three LeetCode problems. Each problem introduced a different application of Trie.

Problem 1: LC 208 — Implement Trie (Prefix Tree)

Difficulty: Medium

What does the problem ask?

We need to design a Trie data structure that supports three operations:

1. insert(word): Insert a word into the Trie.
2. search(word): Check whether the complete word exists in the Trie.
3. startsWith(prefix): Check whether any previously inserted word starts with the given prefix.

For example:

Trie trie;

trie.insert("apple");trie.search("apple");     // true
trie.search("app");       // false
trie.startsWith("app");   // truetrie.insert("app");trie.search("app");       // true

Notice the difference between search() and startsWith().

Although "app" is a prefix of "apple", it is not initially a complete word in the Trie. Therefore, search("app") returns false, while startsWith("app") returns true.

Approach: Basic Trie Implementation

I implemented a custom Node class containing:

• An array of 26 child pointers.
• A boolean isEnd to identify the end of a complete word.

I maintained a root pointer and implemented all three operations using iterative traversal.

The insertion operation creates nodes when they do not exist, while searching follows the existing character paths.

Key Learning: Understanding the Trie node structure, character mapping, and the importance of the isEnd flag.

LeetCode 208 — Implement Trie

Press enter or click to view image in full size

Problem 2: LC 211 — Design Add and Search Words Data Structure

Difficulty: Medium

What does the problem ask?

We need to design a data structure that supports two operations:

1. addWord(word): Add a word to the data structure.
2. search(word): Check whether a word exists in the data structure.

However, there is an additional condition: the search operation supports the . character as a wildcard.

The . character can represent any single character.

For example:

addWord("bad");
addWord("dad");
addWord("mad");

search("pad");  // false
search("bad");  // true
search(".ad");  // true
search("b..");  // true

Here:

• "pad" returns false because no matching word exists.
• "bad" returns true because the exact word exists.
• ".ad" returns true because . can represent b, d, or m.
• "b.." returns true because the two dots can represent a and d.

Approach: Trie + DFS + Backtracking

The insertion operation works exactly like the basic Trie implementation in LC 208.

The main challenge is handling the wildcard character during searching.

We handle two cases:

Case 1: Current character is not .

• Calculate the character index.
• Check whether the corresponding child exists.
• If it does not exist, return false.
• Otherwise, recursively search the next character.

Case 2: Current character is .

Since the dot can represent any character, we cannot follow just one child.

Instead, we explore all existing children using DFS.

If any recursive path successfully matches the remaining characters, we return true.

Once we process the entire search word, we check whether the current node has isEnd = true.

Key Learning: This problem taught me how to combine Trie with DFS and Backtracking to handle wildcard-based searching.

LeetCode 211 — Design Add and Search Words Data Structure

Press enter or click to view image in full size

Problem 3: LC 1268 — Search Suggestions System

Difficulty: Medium

What does the problem ask?

We are given:

• An array of product names.
• A string called searchWord.

We need to build a search suggestion system.

As the user types each character of the search word, we must display up to three product suggestions that match the current prefix.

The suggestions must be in lexicographical (dictionary) order.

For example:

products = {
    "mobile",
    "mouse",
    "moneypot",
    "monitor",
    "mousepad"
};

searchWord = "mouse";

The expected output is:

[
    ["mobile", "moneypot", "monitor"],
    ["mobile", "moneypot", "monitor"],
    ["mouse", "mousepad"],
    ["mouse", "mousepad"],
    ["mouse", "mousepad"]
]

Approach: Trie + Sorting + Suggestions

I followed these steps:

1. Sort all products lexicographically.
2. Insert every product into the Trie.
3. Each Trie node maintains a list of at most three suggestions.
4. During insertion, add the current product to the suggestion list of every node along its path, provided the list contains fewer than three products.
5. Since products are inserted in sorted order, the first three stored products are already the lexicographically smallest suggestions.
6. Traverse the Trie according to the search word, character by character.
7. After reaching each prefix node, return its stored suggestions.

If a character path does not exist, return an empty list for that prefix and all remaining prefixes.

Key Learning: This problem demonstrated how Trie can be extended to build an autocomplete system by storing useful information at every prefix node.

LeetCode 1268 — Search Suggestions System

Press enter or click to view image in full size

Final Takeaway

These three problems helped me understand Trie from three different perspectives:

• LC 208: How to implement and operate a Trie.
• LC 211: How to handle wildcard characters using DFS and Backtracking.
• LC 1268: How to use Trie for real-world autocomplete and search suggestions.

This revision reinforced an important DSA lesson: learning a data structure is not just about understanding its implementation, but also about recognizing how to adapt it to solve different problems.

6. What I Learned from These Three Problems

These three problems helped me understand how the same Trie data structure can be adapted to solve different problems.

The interesting part is that the underlying Trie structure remains almost the same, but the searching logic changes according to the problem requirements.

Conclusion

Trie is one of the important data structures for string and prefix-based problems.

Initially, understanding the node structure, child pointers, and isEnd flag is essential. Once these fundamentals are clear, we can extend Trie with DFS, Backtracking, Sorting, and other techniques to solve more complex problems.

My biggest takeaway from revising Trie is that understanding the structure is only the first step; learning how to adapt it to different problem requirements is what makes it powerful.

👋 Connect with Me:
🔎LEETCODE :- https://leetcode.com/u/HARSHJAISWAL2707/

👤LinkedIn :- https://www.linkedin.com/in/mr-harsh-jaiswal-76691a32a/

Written by Mr. Harsh Jaiswal — B.Tech CSE | DSA & Web Development

#Tries #Leetcode #DSA #CodingInterview #EnjoyProblems