Build challenges · 4 steps · javascript · python

Prefix Tree (Trie)

Construct an n-ary Prefix Tree with character node branching, word insertion, prefix search, and auto-complete.

A Trie (derived from "retrieval") is an ordered tree data structure where each node represents a character along a shared prefix path.

Unlike a standard hash map, a Trie can search prefixes, list auto-complete recommendations, and match wildcards in $O(k)$ time proportional only to the word length $k$.

In this build, you will construct a Trie from scratch:

  1. Implement node chaining and word insertion (insert).
  2. Search for exact whole words (search).
  3. Match prefix substrings (startsWith).
  4. Implement recursive auto-complete suggestions (autocomplete).

The workspace

These files carry across every step. What you write in one step is what you start the next with.

Steps · 0 of 4 done

  1. TrieNode & Word Insertion
  2. Exact Word Search
  3. Prefix Matching (startsWith)
  4. Auto-Complete Suggestions

Start anywhere. Open step 3 first and you are handed the reference build of steps 1 and 2, so every step stands on its own. Nothing here is locked behind anything else.

This build applies Tries and Trees. Read the lesson first if it is unfamiliar — a recommendation, not a prerequisite.

Shorter practice on the same ideas