Implement Trie (Prefix Tree)

medium trie design

Problem

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

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; }
};

Explanation

A trie is a tree where each node holds a map of children keyed by a single character. Words that share a prefix share the same path near the root and only branch where they start to differ, which is what makes prefix questions fast.

insert walks the word character by character, creating a child node whenever one is missing, and at the end sets an end-of-word flag on the final node. That flag is the difference between a stored whole word and a path that merely passes through.

Both search and startsWith share a helper _walk that follows the characters from the root and returns the node it lands on, or nothing if any character has no edge. search additionally requires that landing node's end flag to be set; startsWith is happy as long as the path simply exists.

Example: insert ant and and (they share an). search("and") walks a→n→d and finds the end flag, so it returns true. startsWith("an") just needs the a→n path to exist, which it does, so true as well.

Every operation touches one node per character, so each runs in O(L) time for a key of length L.

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