Implement Trie (Prefix Tree) — Editorial

Opening the reading…

Intuitionone character per edge, one fact stored at the last node

A word can be represented as a path from a root: the first character chooses the first edge, the second character chooses the next edge, and so on. Words with the same prefix share that part of the path. For example, apple and app use the same nodes for a, p, and p; apple only continues with l and e.

The path alone cannot distinguish a complete word from a prefix of a longer word. The node after the final p must therefore store a separate isEnd flag. Searching apple follows all five characters and checks that flag. Searching app follows only three characters and sees that the flag is false until app is inserted. startsWith is different only because reaching the final prefix node is enough; it does not require isEnd to be true.

Approach

Create a root TrieNode with 26 child pointers and an isEnd flag. The root represents the empty prefix, so every operation can begin from the same place.

For insert, start at the root and convert each lowercase character c to index c - 'a'. Create the missing child at that index before moving to it; without this step, a word whose path has not appeared before cannot be stored.

After the final character, set node->isEnd to true. This records the whole word without affecting longer words that continue through the same node, and inserting the same word again remains harmless.

For search, follow every character and return false immediately when the required child is missing. A missing edge proves that no inserted word can equal the requested word or share its entire path.

After search consumes all characters, return node->isEnd rather than merely returning true. The path for app can exist only because apple was inserted, but that does not make app an inserted word.

For startsWith, follow the prefix in exactly the same way, returning false on a missing child. If every character is found, return true without checking isEnd because a longer inserted word may provide the prefix.

Process operations in order, recreating the trie when Trie appears and appending the required string after every operation. Keeping the state between calls is what makes later searches observe earlier insertions.

Complexityshared prefixes reduce allocation, but never increase traversal length

MEASURE	BOUND	WHY
Time	O(A)	Each operation examines each character in its argument once and performs constant-time array access. Summing those walks over the complete operation sequence counts each processed character once, so no character is charged twice.
Space	O(P), at most O(A)	The result strings are required output and are excluded from extra space. Each newly created node represents one previously missing prefix; shared prefixes reuse nodes, while the worst shape creates a new node for every inserted character, giving O(A) extra space.

A is the total number of characters across all insert, search, and startsWith arguments. P is the number of trie nodes allocated, including the root. The alphabet has fixed size 26, so each node's child array is constant-sized.

Annotated solutionC++ · fixed 26-child nodes · complete judge-ready implementation

CPPThe root starts every walk, isEnd handles exact words, and missing children reject impossible paths.

#include <string>
#include <vector>

using namespace std;

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

    TrieNode() : isEnd(false) {
        for (int i = 0; i < 26; ++i) {
            children[i] = nullptr;
        }
    }

    ~TrieNode() {
        for (int i = 0; i < 26; ++i) {
            delete children[i];
        }
    }
};

class Trie {
public:
    TrieNode* root;

    Trie() : root(new TrieNode()) {}

    ~Trie() {
        delete root;
    }

    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }

    bool search(const string& word) const {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return node->isEnd;
    }

    bool startsWith(const string& prefix) const {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return true;
    }
};

class Solution {
public:
    vector<string> process(vector<string>& operations,
                           vector<vector<string>>& args) {
        Trie* trie = nullptr;
        vector<string> result;

        for (int i = 0; i < static_cast<int>(operations.size()); ++i) {
            const string& operation = operations[i];

            if (operation == "Trie") {
                delete trie;
                trie = new Trie();
                result.push_back("null");
            } else if (operation == "insert") {
                trie->insert(args[i][0]);
                result.push_back("null");
            } else if (operation == "search") {
                result.push_back(trie->search(args[i][0]) ? "true" : "false");
            } else if (operation == "startsWith") {
                result.push_back(trie->startsWith(args[i][0]) ? "true" : "false");
            }
        }

        delete trie;
        return result;
    }
};

The insertion line that creates a child must appear before node moves forward. Once node points at the child, setting isEnd after the loop marks exactly the node for the complete word. The two query methods deliberately share the same traversal but end differently: search asks whether a word stops here, while startsWith asks only whether this path exists.

A sparse-child alternativeless fixed memory per node, more work per character

A fixed array is a natural choice for 26 lowercase letters because indexing is simple and predictable. A competent alternative stores only existing edges in an unordered_map. This can use less memory when most trie nodes have very few children, but each character now pays hashing and map-allocation overhead. It is a memory-oriented rearrangement, not an asymptotic improvement: traversal remains linear in the argument length.

CPPA standalone sparse-child version that stores only edges that actually occur.

#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

class SparseTrieNode {
public:
    unordered_map<char, SparseTrieNode*> children;
    bool isEnd = false;

    ~SparseTrieNode() {
        for (auto& entry : children) {
            delete entry.second;
        }
    }
};

class SparseTrie {
public:
    SparseTrieNode* root = new SparseTrieNode();

    ~SparseTrie() {
        delete root;
    }

    void insert(const string& word) {
        SparseTrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new SparseTrieNode();
            }
            node = node->children[c];
        }
        node->isEnd = true;
    }

    bool search(const string& word) const {
        const SparseTrieNode* node = root;
        for (char c : word) {
            auto it = node->children.find(c);
            if (it == node->children.end()) {
                return false;
            }
            node = it->second;
        }
        return node->isEnd;
    }

    bool startsWith(const string& prefix) const {
        const SparseTrieNode* node = root;
        for (char c : prefix) {
            auto it = node->children.find(c);
            if (it == node->children.end()) {
                return false;
            }
            node = it->second;
        }
        return true;
    }
};

class Solution {
public:
    vector<string> process(vector<string>& operations,
                           vector<vector<string>>& args) {
        SparseTrie* trie = nullptr;
        vector<string> result;

        for (int i = 0; i < static_cast<int>(operations.size()); ++i) {
            const string& operation = operations[i];

            if (operation == "Trie") {
                delete trie;
                trie = new SparseTrie();
                result.push_back("null");
            } else if (operation == "insert") {
                trie->insert(args[i][0]);
                result.push_back("null");
            } else if (operation == "search") {
                result.push_back(trie->search(args[i][0]) ? "true" : "false");
            } else if (operation == "startsWith") {
                result.push_back(trie->startsWith(args[i][0]) ? "true" : "false");
            }
        }

        delete trie;
        return result;
    }
};