Trie Delete — Editorial

Opening the reading…

Intuitiondeletion changes word endings before it changes the trie shape

A trie represents a word in two separate ways: its characters select a path from the root, and a terminal marker says that the path itself is a complete word. This distinction is the key to deletion. If you remove the marker for the, the path t -> h -> e must remain when there, their, or another longer word still uses it.

After clearing the marker, inspect the key's path from the end toward the root. A node can be freed only when it is not the end of another word and has no children. The first node that fails either test protects every earlier prefix, because that node is still needed by some word.

Approach

Create a root node and insert every word, marking only its final node as terminal, because a path without a terminal marker is merely a prefix and must not appear as a word.

While inserting, reuse an existing child when the next character is already present, because separate copies of a shared prefix would hide which nodes are still needed.

Follow key from the root while recording every node on its path, and stop without changing anything if a child is missing, because an absent key was never a trie word.

Check the final node's terminal marker before deleting it, because reaching the characters of key is not enough when key is only a prefix of another word.

Clear the final terminal marker, because this removes exactly key while preserving the path for longer words and any other word ending at a different node.

Walk backward over the recorded path and delete a child only when it is non-terminal and has no children, because either condition proves that some remaining word still depends on it.

Search every original word after deletion and append successful searches in the original order, because the trie stores membership while the required result also preserves the input ordering.

ComplexityS is the total number of characters in words and L is the maximum key length

MEASURE	BOUND	WHY
Time	O(S + L)	Insertion and the final membership scan each process every input character a constant number of times, for O(S) total. Deletion visits at most L path nodes and checks 26 child slots per node; 26 is constant, so that work is O(L).
Space	O(S) extra	The trie has at most one node per inserted character plus the root, so it uses O(S) working memory; the recorded deletion path adds O(L). The returned vector is required output and is excluded. A trie-shaped input with no shared prefixes reaches the worst bound of O(S), while a highly shared input uses fewer nodes.

Here S is the sum of the lengths of all words in words, and L is the maximum of the key length and any word length. The alphabet size is fixed at 26.

Annotated solutionC++ · explicit path recording and backward pruning

CPPA complete trie solution that clears one terminal marker, prunes backward, and preserves input order.

#include <string>
#include <vector>
using namespace std;

class Solution {
    struct Node {
        Node* child[26];
        bool terminal;

        Node() : terminal(false) {
            for (int i = 0; i < 26; ++i) {
                child[i] = nullptr;
            }
        }
    };

    Node* root;

    bool hasChild(Node* node) {
        for (int i = 0; i < 26; ++i) {
            if (node->child[i] != nullptr) return true;
        }
        return false;
    }

    void insertWord(const string& word) {
        Node* current = root;
        for (char letter : word) {
            int index = letter - 'a';
            if (current->child[index] == nullptr) {
                current->child[index] = new Node();
            }
            current = current->child[index];
        }
        current->terminal = true;
    }

    bool searchWord(const string& word) const {
        Node* current = root;
        for (char letter : word) {
            int index = letter - 'a';
            if (current->child[index] == nullptr) return false;
            current = current->child[index];
        }
        return current->terminal;
    }

    void eraseWord(const string& key) {
        Node* current = root;
        vector<Node*> path(key.size() + 1);
        path[0] = root;

        for (int i = 0; i < static_cast<int>(key.size()); ++i) {
            int index = key[i] - 'a';
            if (current->child[index] == nullptr) return;
            current = current->child[index];
            path[i + 1] = current;
        }

        if (!current->terminal) return;
        current->terminal = false;

        for (int i = static_cast<int>(key.size()) - 1; i >= 0; --i) {
            Node* parent = path[i];
            int index = key[i] - 'a';
            Node* child = parent->child[index];

            if (child->terminal || hasChild(child)) break;

            delete child;
            parent->child[index] = nullptr;
        }
    }

public:
    vector<string> deleteKey(vector<string> words, string key) {
        root = new Node();

        for (const string& word : words) {
            insertWord(word);
        }

        eraseWord(key);

        vector<string> remaining;
        for (const string& word : words) {
            if (searchWord(word)) {
                remaining.push_back(word);
            }
        }
        return remaining;
    }
};

The terminal check must happen before pruning, and the pruning loop must move from the key's last character toward the root. Clearing the marker handles the logical deletion; the backward loop is only memory cleanup. Its break condition is deliberately conservative: once a node is terminal or has any child, every earlier node on the path is also still needed by a surviving word.