Trie Operations: Insert, Search, and startsWith

A trie exposes three fundamental operations: insert a word, search for an exact word, and startsWith to test whether any stored word begins with a given prefix. All three walk the tree character by character and run in O(L) time, where L is the length of the word or prefix. This page assumes the TrieNode and Trie class from implementing a trie.

Insert

To insert a word, start at the root and walk one character at a time. For each character, follow the existing child if present, or create a new node if the path does not exist yet. After the last character, set isEnd = true to mark the word’s end.

void insert(const std::string& word) {
    TrieNode* node = root;
    for (char ch : word) {
        if (!node->children.count(ch))
            node->children[ch] = new TrieNode();
        node = node->children[ch];
    }
    node->isEnd = true;
}

public void insert(String word) {
    TrieNode node = root;
    for (char ch : word.toCharArray()) {
        node.children.putIfAbsent(ch, new TrieNode());
        node = node.children.get(ch);
    }
    node.isEnd = true;
}

insert(word) {
  let node = this.root;
  for (const ch of word) {
    if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
    node = node.children.get(ch);
  }
  node.isEnd = true;
}

def insert(self, word):
    node = self.root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
    node.is_end = True

Complexity: O(L) time, O(L) space in the worst case (a brand-new word with no shared prefix creates up to L nodes).

A shared helper: walk to a node

Both search and startsWith need the same first step: follow the characters of a string and return the node you land on, or “nothing” if the path breaks. It is worth isolating that walk.

TrieNode* findNode(const std::string& s) {
    TrieNode* node = root;
    for (char ch : s) {
        auto it = node->children.find(ch);
        if (it == node->children.end()) return nullptr;
        node = it->second;
    }
    return node;
}

private TrieNode findNode(String s) {
    TrieNode node = root;
    for (char ch : s.toCharArray()) {
        node = node.children.get(ch);
        if (node == null) return null;
    }
    return node;
}

findNode(s) {
  let node = this.root;
  for (const ch of s) {
    if (!node.children.has(ch)) return null;
    node = node.children.get(ch);
  }
  return node;
}

def _find_node(self, s):
    node = self.root
    for ch in s:
        if ch not in node.children:
            return None
        node = node.children[ch]
    return node

Search (exact word)

Searching for a complete word is the walk, plus one extra check: the node you land on must have isEnd == true. Otherwise the string is only a prefix of some stored word, not a stored word itself.

bool search(const std::string& word) {
    TrieNode* node = findNode(word);
    return node != nullptr && node->isEnd;
}

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

search(word) {
  const node = this.findNode(word);
  return node !== null && node.isEnd;
}

def search(self, word):
    node = self._find_node(word)
    return node is not None and node.is_end

Complexity: O(L) time, O(1) extra space.

Pitfall: Returning true just because the walk succeeded is the classic trie bug. If card is stored but car was never inserted, the path for car exists, yet search("car") must return false. Always check isEnd.

startsWith (prefix test)

startsWith is even simpler than search: if the path exists at all, some word goes through it, so return whether the walk reached a node. The isEnd flag is irrelevant here.

bool startsWith(const std::string& prefix) {
    return findNode(prefix) != nullptr;
}

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

startsWith(prefix) {
  return this.findNode(prefix) !== null;
}

def starts_with(self, prefix):
    return self._find_node(prefix) is not None

Complexity: O(L) time, O(1) extra space.

Summary of costs

Operation       Time    Space
--------------  ------  ---------------------
insert          O(L)    O(L) new nodes worst
search          O(L)    O(1)
startsWith      O(L)    O(1)

Every cost depends only on the query length L, never on the number of stored words n — the headline advantage of a trie over scanning a hash set.

For beginners: Notice how search and startsWith share the same walk and differ by a single line. Understanding that difference — “did a word end here?” versus “does the path exist?” — is the key to tries.

Now put these to work in trie applications, or test yourself with the trie exercises.