Build a Prefix Tree

medium trie design

Problem

Implement a prefix tree (trie) supporting three operations: insert(word), search(word) (true if the exact word was inserted), and startsWith(prefix) (true if any inserted word begins with the prefix). Each node carries an end-of-word flag and a map of child characters.

Inputinsert "ant", insert "and", search "and", startsWith "an"

Outputtrue, true

Both words share the prefix "an". Search returns true only for inserted whole words.

operations (one per line: insert/search/prefix word)

class Trie:
    def __init__(self):
        self.root = {"end": False, "kids": {}}
    def insert(self, w):
        n = self.root
        for c in w:
            n["kids"].setdefault(c, {"end": False, "kids": {}})
            n = n["kids"][c]
        n["end"] = True
    def _walk(self, w):
        n = self.root
        for c in w:
            if c not in n["kids"]: return None
            n = n["kids"][c]
        return n
    def search(self, w):
        n = self._walk(w); return bool(n and n["end"])
    def starts_with(self, p):
        return self._walk(p) is not None

class Trie {
  constructor() { this.root = { end: false, kids: {} }; }
  insert(w) {
    let n = this.root;
    for (const c of w) { if (!n.kids[c]) n.kids[c] = { end: false, kids: {} }; n = n.kids[c]; }
    n.end = true;
  }
  _walk(w) { let n = this.root; for (const c of w) { if (!n.kids[c]) return null; n = n.kids[c]; } return n; }
  search(w) { const n = this._walk(w); return !!(n && n.end); }
  startsWith(p) { return this._walk(p) !== null; }
}

class Trie {
    private static class Node {
        boolean end;
        Map<Character, Node> kids = new HashMap<>();
    }
    private Node root = new Node();
    public void insert(String w) {
        Node n = root;
        for (char c : w.toCharArray()) {
            n.kids.computeIfAbsent(c, k -> new Node());
            n = n.kids.get(c);
        }
        n.end = true;
    }
    private Node walk(String w) {
        Node n = root;
        for (char c : w.toCharArray()) {
            if (!n.kids.containsKey(c)) return null;
            n = n.kids.get(c);
        }
        return n;
    }
    public boolean search(String w) {
        Node n = walk(w); return n != null && n.end;
    }
    public boolean startsWith(String p) {
        return walk(p) != null;
    }
}

class Trie {
    struct Node {
        bool end = false;
        unordered_map<char, Node*> kids;
    };
    Node* root = new Node();
public:
    void insert(string w) {
        Node* n = root;
        for (char c : w) {
            if (!n->kids.count(c)) n->kids[c] = new Node();
            n = n->kids[c];
        }
        n->end = true;
    }
    Node* walk(string w) {
        Node* n = root;
        for (char c : w) {
            if (!n->kids.count(c)) return nullptr;
            n = n->kids[c];
        }
        return n;
    }
    bool search(string w) { Node* n = walk(w); return n != nullptr && n->end; }
    bool startsWith(string p) { return walk(p) != nullptr; }
};

Time: O(L) per operation Space: O(total characters inserted)