Implement Trie Prefix Tree DSA Solution

Learning Outcome

After this lesson, you should be able to model words as paths and separate full-word search from prefix search.

Problem Statement

Design a Trie with insert, search, and startsWith operations.

Input	Output	Why
`insert("apple"), search("apple"), search("app"), startsWith("app")`	`true, false, true`	apple is a complete word, while app is only a prefix until it is inserted separately.

Brute Force Approach

Store every word in a list or set and scan words for prefix checks. This is simple but prefix search can depend on the number of stored words.

Optimized Approach

Use a tree of character nodes. Each word follows a path from the root, and an isWord marker records where a complete word ends.

Exact Pseudocode

root = empty node
insert(word):
  node = root
  for ch in word:
    if child ch is missing:
      create child ch
    node = child ch
  node.isWord = true

search(word):
  node = walk word from root
  return node exists and node.isWord

startsWith(prefix):
  return walk prefix from root exists

Reference Code

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["#"] = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return "#" in node

    def startsWith(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return False
            node = node[ch]
        return True

Sample Dry Run

Step	State	Result
insert apple	Create path a to p to p to l to e	mark e as word end
search apple	Path exists and word marker is true	true
search app	Path exists but word marker is false	false
startsWith app	Path exists	true

Complexity

Measure	Value	Reason
Time	O(length of word)	Each operation walks at most one character path.
Space	O(total stored characters)	Nodes store the shared prefixes of inserted words.

Edge Cases

Searching a prefix should be false unless that prefix was inserted as a full word.
startsWith should not require isWord.
Empty string behavior should match the prompt.

Interview Checklist

Use a root node that represents no character.
Create missing children during insert only.
Keep isWord separate from prefix existence.

FAQs

Why do we need isWord?

Without isWord, search("app") and startsWith("app") would look identical after inserting "apple".

When is Trie better than a hash set?

Trie is useful when prefix operations are first-class, not only exact-word lookup.

What is the core pattern?

Prefix tree traversal.

Implement Trie: Prefix Tree Pattern