Trie Delete

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

1. 1Create 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.
2. 2While 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.
3. 3Follow 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.
4. 4Check 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.
5. 5Clear 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.
6. 6Walk 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.
7. 7Search 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

Annotated solutionC++ · explicit path recording and backward pruning

#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.

Common mistakesthe two deletion decisions that change the result