FAANGPrep Sprint

Implement Trie (Prefix Tree)

Design a data structure that supports insert, search, and startsWith.

MediumSolve on LeetCode

Problem Description

Implement Trie class:

insert(word): Inserts string word.
search(word): Returns true if string word is in the trie.
startsWith(prefix): Returns true if there is a previously inserted string having prefix.

Interactive Visualization

GREEN = END OF A STORED WORD

INSERT

Operation

insert("apple")

Nodes

Returns

—

insert("apple"): start at the root

the root has no 'a' child: create one

Operations

Legend & Complexity

The node the operation is on

The path this operation has walked

A node marked as the end of an inserted word

No child for the next character: search or startsWith returns false

Each operation

O(L)

Space

O(total chars)

Watch how insert creates new nodes only when necessary, and search traverses existing paths.

Algorithm Strategy

Node Structure: Each node contains a map/array of size 26 (for 'a'-'z') and a boolean isEnd.
Insert: Traverse down; create nodes if missing. Mark last node as isEnd.
Search: Traverse down; if node missing -> return false. At end, return node.isEnd.
StartsWith: Traverse down; if node missing -> return false. If loop finishes, return true.

Dry Run: Insert 'cat'

Char	Node Exists?	Action
'c'	No	Create 'c' node. Move to 'c'.
'a'	No	Create 'a' node. Move to 'a'.
't'	No	Create 't' node. Move to 't'.
End	-	Mark 't' node as `isEnd=True`.

Solution

O(L) Time per operation where L is word length.

Implement Trie (Prefix Tree) Code

1var Trie = function() {
2    this.children = {};
3    this.isEnd = false;
4};
5
6Trie.prototype.insert = function(word) {
7    let node = this;
8    for(const char of word) {
9        if(!node.children[char]) {
10            node.children[char] = new Trie();
11        }
12        node = node.children[char];
13    }
14    node.isEnd = true;
15};
16
17Trie.prototype.search = function(word) {
18    let node = this;
19    for(const char of word) {
20        if(!node.children[char]) return false;
21        node = node.children[char];
22    }
23    return node.isEnd;
24};
25
26Trie.prototype.startsWith = function(prefix) {
27    let node = this;
28    for(const char of prefix) {
29        if(!node.children[char]) return false;
30        node = node.children[char];
31    }
32    return true;
33};

Edge Cases & Common Mistakes

Check for:

Word is Prefix: Searching for 'app' when 'apple' exists. Should return False (unless 'app' was inserted independently).
Prefix Search: startsWith('app') should return True if 'apple' exists.
Duplication: Inserting 'app' twice shouldn't break anything.

Previous Problem

Gas Station

Next Problem

Search Suggestions System