Faangprep Logo
Log inStart free
Browse curriculum

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

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

Algorithm Strategy

  1. Node Structure: Each node contains a map/array of size 26 (for 'a'-'z') and a boolean isEnd.
  2. Insert: Traverse down; create nodes if missing. Mark last node as isEnd.
  3. Search: Traverse down; if node missing -> return false. At end, return node.isEnd.
  4. 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

Introduction to Tries (Prefix Trees)

Next

Prefix Matching

The approach, step by step

  1. insert

    Walk the word from the root, creating each missing child, and mark the last node as a word end.

  2. search

    Walk the word; return false at a missing child, otherwise return the last node’s end-of-word flag.

  3. startsWith

    Walk the prefix; return false at a missing child, otherwise return true.

Frequently asked questions

What is the difference between search and startsWith in a trie?

Both walk the path for their input one character at a time and return false if a character is missing. search then returns whether the last node is marked as the end of a word, while startsWith returns true as soon as the path exists.

Why does insert need an end-of-word flag?

Without it, storing "apple" would make "app" look present, because its path exists inside apple’s. The flag on the final node records that a whole word was inserted there.

What is the time and space complexity of a trie?

insert, search and startsWith each take O(L) time for a word or prefix of length L. The trie keeps one node per character not shared with an earlier word, so space is O(total characters inserted).

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description