Typorithm · medium

Trie Search & Prefix

trie-searchtrieslookupprefix-querywalk

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Trie Search & Prefix

Tries

Both search and startsWith walk the prefix path; search additionally requires the final node's isEnd flag.

Searching a trie reuses one helper that walks character by character and returns the final node or null.

A full-word search succeeds only when that node exists and is marked as a word end.

A prefix query succeeds as soon as the path exists, regardless of the isEnd flag.

Shared walk helper returns node or null.

search needs node.isEnd.

startsWith only needs the path to exist.

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

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

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

Read the implementation

Connect each part of the code to the concept before you type.

1. Walk the path

find returns the node at the end of the path, or null.

const node = this.find(word)

2. Full word check

A word exists only if the path ends on a word terminal.

return node !== null && node.isEnd

3. Prefix check

Any reachable path means the prefix exists.

return this.find(prefix) !== null

4. Dead end

A missing character means the path does not exist.

if (!node.children.has(ch)) {
      return null;
    }

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.