Implement Trie (Prefix Tree)

Approach Summary

Each node has a children map and an isEnd flag. Insert adds nodes char by char. Search/startsWith traverse the trie.

Full Solution & Approach

A trie is an n-ary tree where each node holds a child map (character → node) and a boolean flag marking whether a word ends here. Insert: walk from the root, creating child nodes on demand, then set is_end on the final node. Search: walk the same path; if any character is missing, the word cannot exist — return false; otherwise the word exists only if is_end is true on the final node (a prefix that is not a full word must return false). startsWith: identical to search but returns true as long as the path exists, ignoring is_end. The child map gives O(1) average lookup per character, so every operation costs O(L), where L is the word length. This is the classic trade: space for speed — a node exists for every distinct prefix, so total nodes are at most the total characters across all inserted words.

Each operation touches one node per character with O(1) map lookups — O(L) time where L is the string length. Worst-case space is the total number of characters inserted — O(total characters).

Solution Code

Solution

class Trie:
    def __init__(self):
        self.children = {}
        self.is_end = False

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            if ch not in node.children:
                node.children[ch] = Trie()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, word: str):
        node = self
        for ch in word:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

class Trie {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
  insert(word) {
    let node = this;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new Trie();
      node = node.children[ch];
    }
    node.isEnd = true;
  }
  _find(word) {
    let node = this;
    for (const ch of word) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }
  search(word) {
    const node = this._find(word);
    return !!node && node.isEnd;
  }
  startsWith(prefix) {
    return this._find(prefix) !== null;
  }
}

class Trie {
    private final Trie[] children = new Trie[26];
    private boolean isEnd;

    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) node.children[c - 'a'] = new Trie();
            node = node.children[c - 'a'];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = find(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    private Trie find(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) return null;
            node = node.children[c - 'a'];
        }
        return node;
    }
}

class Trie {
    Trie* children[26] = {};
    bool isEnd = false;

public:
    void insert(const string& word) {
        Trie* node = this;
        for (char c : word) {
            if (!node->children[c - 'a']) node->children[c - 'a'] = new Trie();
            node = node->children[c - 'a'];
        }
        node->isEnd = true;
    }

    bool search(const string& word) {
        Trie* node = find(word);
        return node && node->isEnd;
    }

    bool startsWith(const string& prefix) {
        return find(prefix) != nullptr;
    }

private:
    Trie* find(const string& word) {
        Trie* node = this;
        for (char c : word) {
            if (!node->children[c - 'a']) return nullptr;
            node = node->children[c - 'a'];
        }
        return node;
    }
};

Edge Cases to Watch

Searching for a prefix that is not a complete word — the is_end check is essential
Inserting the same word twice — idempotent
Inserting a word then searching for its prefix — false unless the prefix was also inserted as a word
Empty string — the root's is_end flag distinguishes it

How to Recognize This Pattern

Prefix queries
Word dictionary design

Complexity Analysis

Time Complexity

O(m) per operation

Space Complexity

O(ALPHABET × n × m)