Trie / Prefix Tree

A–Z

Dictionary12

app

apple

application

apply

apt

ball

ban

band

bat

can

cap

cat

Default

Word End

Active

Found

Not Found

Time

O(L + K)

Space

O(N×L)

Debugger · v1.0

LIVE

1function autocomplete(prefix) {

2 let node = root;

3 for (const char of prefix) {

4 if (!node.children[char]) return [];

5 node = node.children[char];

6 }

7 const results = [];

8 dfs(node, prefix, results);

9 return results;

10}

12function dfs(node, word, results) {

13 if (node.isEnd) results.push(word);

14 for (const [c, child] of node.children)

15 dfs(child, word + c, results);

16}

Debugger · v1.0

LIVE

1function autocomplete(prefix) {

2 let node = root;

3 for (const char of prefix) {

4 if (!node.children[char]) return [];

5 node = node.children[char];

6 }

7 const results = [];

8 dfs(node, prefix, results);

9 return results;

10}

12function dfs(node, word, results) {

13 if (node.isEnd) results.push(word);

14 for (const [c, child] of node.children)

15 dfs(child, word + c, results);

16}

State Inspector

No variables in scope.

Prefix:

Trie Visualizer

Trie — Autocomplete

Step 1 of 6

Autocomplete is one of the most practical Trie applications. Pick a prefix and watch the algorithm walk the prefix path, then DFS-collect every word reachable from that point.

How Autocomplete Works

Phase 1: walk the prefix char-by-char (O(L)). If any char is missing, return []. Phase 2: DFS from the prefix endpoint — every node with isEnd=true is a valid completion.

prefix = "ap"

["app","apple","apply","application","apt"]

prefix = "ba"

["ball","bat","band","ban"]

prefix = "ca"

["cat","can","cap"]