Trie — Core Operations

class Trie {
    struct Node {
        Node* children[26] = {};   // a-z, all null
        bool isEnd = false;
    };
    Node* root = new Node();
public:
    void insert(const string& word) {
        Node* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (!cur->children[i]) cur->children[i] = new Node();
            cur = cur->children[i];
        }
        cur->isEnd = true;
    }
    bool search(const string& word) {
        Node* n = walk(word);
        return n && n->isEnd;          // path exists AND marked end-of-word
    }
    bool startsWith(const string& prefix) {
        return walk(prefix) != nullptr; // path exists (flag irrelevant)
    }
private:
    Node* walk(const string& s) {
        Node* cur = root;
        for (char c : s) {
            int i = c - 'a';
            if (!cur->children[i]) return nullptr;
            cur = cur->children[i];
        }
        return cur;
    }
};

class TrieNode:
    def __init__(self):
        self.children = {}        # char -> TrieNode (map: only used chars)
        self.is_end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.is_end = True
 
    def _walk(self, s: str):
        cur = self.root
        for c in s:
            if c not in cur.children:
                return None
            cur = cur.children[c]
        return cur
 
    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end
 
    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

class Trie {
    static class Node {
        Node[] children = new Node[26];
        boolean isEnd = false;
    }
    private final Node root = new Node();
 
    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) cur.children[i] = new Node();
            cur = cur.children[i];
        }
        cur.isEnd = true;
    }
    public boolean search(String word) {
        Node n = walk(word);
        return n != null && n.isEnd;
    }
    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }
    private Node walk(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) return null;
            cur = cur.children[i];
        }
        return cur;
    }
}

def words_with_prefix(self, prefix: str) -> list[str]:
    node = self._walk(prefix)
    if node is None:
        return []
    out = []
    def dfs(n, path):
        if n.is_end:
            out.append(prefix + path)
        for c, child in sorted(n.children.items()):   # sorted -> lexicographic
            dfs(child, path + c)
    dfs(node, "")
    return out

def delete(self, word: str) -> None:
    def helper(node, i):
        if i == len(word):
            node.is_end = False          # unmark; node may still be a prefix
            return len(node.children) == 0
        c = word[i]
        child = node.children.get(c)
        if child is None:
            return False                 # word not present
        should_prune = helper(child, i + 1)
        if should_prune and not child.is_end:
            del node.children[c]          # remove the now-useless child
        return len(node.children) == 0 and not node.is_end
    helper(self.root, 0)