Implement Trie (Prefix Tree) - Practice Coding Problems

Implement Trie (Prefix Tree) - Problem

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Input & Output

Example 1 — Basic Trie Operations

$ Input: operations = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"], values = ["", "apple", "apple", "app", "app", "app", "app"]

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

💡 Note: Create trie, insert "apple", search "apple" (found), search "app" (not found), check prefix "app" (exists), insert "app", search "app" (now found)

Example 2 — Multiple Words with Shared Prefix

$ Input: operations = ["Trie", "insert", "insert", "search", "startsWith"], values = ["", "car", "card", "care", "car"]

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

💡 Note: Insert "car" and "card", search "care" (not found), but "car" is a valid prefix

Example 3 — Single Character Operations

$ Input: operations = ["Trie", "insert", "search", "startsWith"], values = ["", "a", "a", "a"]

› Output: [null, null, true, true]

💡 Note: Edge case with single character: insert "a", search "a" (found), "a" starts with "a"

Constraints

1 ≤ word.length, prefix.length ≤ 2000
word and prefix consist only of lowercase English letters
At most 3 × 10⁴ calls in total will be made to insert, search, and startsWith

Visualization

Tap to expand

Understanding the Visualization

Input

Series of operations: insert, search, startsWith with word values

Process

Build tree structure sharing common prefixes between words

Output

Array of results: null for insert, boolean for search/startsWith

Key Takeaway

🎯 Key Insight: A trie shares common prefixes in a tree structure, making prefix operations extremely efficient

Asked in

G Google 45 a Amazon 38 M Microsoft 32 🍎 Apple 25

The key insight is to use a tree structure where each path represents a word prefix, allowing efficient sharing of common prefixes. The optimal approach uses a trie with nodes containing character children and end markers. Time: O(m) per operation, Space: O(ALPHABET_SIZE × N × M) for the tree structure.

Common Approaches

Approach	Time	Space	Notes
✓ Array/List Storage	O(n*m)	O(n*m)	Store all words in a simple array and search linearly
Trie Data Structure	O(m)	O(ALPHABET_SIZE × N × M)	Use a tree structure where each node represents a character and paths represent words

Array/List Storage — Algorithm Steps

Store words in an array
Search by iterating through all words
Check prefixes by comparing each word's beginning

Visualization

Tap to expand

Step-by-Step Walkthrough

Insert

Add words to array sequentially

Check each word in array for exact match

Prefix

Check each word for prefix match

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 1000
#define MAX_WORD_LEN 2000

typedef struct {
    char words[MAX_WORDS][MAX_WORD_LEN];
    int count;
} Trie;

Trie* trieCreate() {
    Trie* trie = (Trie*)malloc(sizeof(Trie));
    trie->count = 0;
    return trie;
}

void trieInsert(Trie* obj, char* word) {
    strcpy(obj->words[obj->count], word);
    obj->count++;
}

bool trieSearch(Trie* obj, char* word) {
    for (int i = 0; i < obj->count; i++) {
        if (strcmp(obj->words[i], word) == 0) {
            return true;
        }
    }
    return false;
}

bool trieStartsWith(Trie* obj, char* prefix) {
    int prefixLen = strlen(prefix);
    for (int i = 0; i < obj->count; i++) {
        if (strncmp(obj->words[i], prefix, prefixLen) == 0) {
            return true;
        }
    }
    return false;
}

char* solution(char operations[][20], char values[][2000], int size, int* returnSize) {
    static char result[10000];
    Trie* trie = NULL;
    char temp[20];
    
    strcpy(result, "[");
    
    for (int i = 0; i < size; i++) {
        if (i > 0) strcat(result, ",");
        
        if (strcmp(operations[i], "Trie") == 0) {
            trie = trieCreate();
            strcat(result, "null");
        } else if (strcmp(operations[i], "insert") == 0) {
            trieInsert(trie, values[i]);
            strcat(result, "null");
        } else if (strcmp(operations[i], "search") == 0) {
            strcat(result, trieSearch(trie, values[i]) ? "true" : "false");
        } else if (strcmp(operations[i], "startsWith") == 0) {
            strcat(result, trieStartsWith(trie, values[i]) ? "true" : "false");
        }
    }
    
    strcat(result, "]");
    *returnSize = strlen(result);
    return result;
}

int main() {
    char operations[100][20];
    char values[100][2000];
    char line1[5000], line2[5000];
    
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    line1[strcspn(line1, "\n")] = 0;
    line2[strcspn(line2, "\n")] = 0;
    
    int opCount = 0, valCount = 0;
    char *token;
    
    char *copy1 = strdup(line1 + 1);
    copy1[strlen(copy1) - 1] = 0;
    token = strtok(copy1, ",");
    while (token != NULL) {
        while (*token == ' ' || *token == '"') token++;
        char *end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"')) end--;
        *(end + 1) = 0;
        strcpy(operations[opCount++], token);
        token = strtok(NULL, ",");
    }
    
    char *copy2 = strdup(line2 + 1);
    copy2[strlen(copy2) - 1] = 0;
    token = strtok(copy2, ",");
    while (token != NULL) {
        while (*token == ' ' || *token == '"') token++;
        char *end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"')) end--;
        *(end + 1) = 0;
        strcpy(values[valCount++], token);
        token = strtok(NULL, ",");
    }
    
    int returnSize;
    char* result = solution(operations, values, opCount, &returnSize);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n*m)

Each operation iterates through n words, each comparison takes O(m) time

✓ Linear Growth

Space Complexity

O(n*m)

Store n words, each of average length m

⚡ Linearithmic Space

339.8K Views

High Frequency

~25 min Avg. Time

8.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Array/List Storage — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler