Implement Trie (Prefix Tree) (LC 208): insert, search, startsWith

Design a Trie class with insert, search and startsWith. Each node holds up to 26 child links and an end-of-word flag, so every operation walks one node per character: O(L) time per call.

Language Selection

Choose your preferred programming language

Showing: Python

Implement Trie (Prefix Tree)

Problem Statement

A trie (also called a prefix tree) stores a set of strings so that both whole words and prefixes can be looked up quickly. It is the data structure behind autocomplete and spell checking.

Build a class Trie with these operations:

  • Trie() creates an empty trie.
  • insert(word) adds the string word to the trie.
  • search(word) returns true if word was inserted earlier (as a whole word), otherwise false.
  • startsWith(prefix) returns true if at least one inserted word begins with prefix, otherwise false.

Examples

Example 1:

Input:
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["cart"], ["cart"], ["car"], ["car"], ["car"], ["car"]]
Output:
[null, null, true, false, true, null, true]
Explanation:
insert("cart")      -> the trie now holds "cart"
search("cart")      -> true
search("car")       -> false: "car" is only a prefix so far
startsWith("car")   -> true: "cart" begins with "car"
insert("car")       -> "car" is now a word too
search("car")       -> true

Example 2:

Input:
["Trie", "insert", "startsWith", "search", "startsWith", "search"]
[[], ["dog"], ["do"], ["do"], ["dot"], ["dogs"]]
Output:
[null, null, true, false, false, false]
Explanation:
"do" is a prefix of "dog" but was never inserted, "dot" is not a prefix of anything,
and "dogs" is longer than any stored word.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix contain only lowercase English letters
  • At most 3 * 10^4 calls in total are made to insert, search and startsWith

Approach 1: Hash Set of Words

Algorithm

Store the inserted words in a hash set. Whole-word lookup is then a single set query; only the prefix query is slow, because it has to check every stored word.

  1. insert(word): add word to the set.
  2. search(word): return whether the set contains word.
  3. startsWith(prefix): scan all stored words and return true as soon as one starts with prefix.

This is useful as a baseline and as a reference to test a real trie against, but startsWith costs time proportional to everything stored.

Implementation

Python:

class Trie:
    def __init__(self):
        self.words = set()

    def insert(self, word: str) -> None:
        self.words.add(word)

    def search(self, word: str) -> bool:
        return word in self.words

    def startsWith(self, prefix: str) -> bool:
        # Linear scan over every stored word
        return any(w.startswith(prefix) for w in self.words)

Java:

import java.util.HashSet;
import java.util.Set;

class Trie {
    private final Set<String> words = new HashSet<>();

    public Trie() {
    }

    public void insert(String word) {
        words.add(word);
    }

    public boolean search(String word) {
        return words.contains(word);
    }

    public boolean startsWith(String prefix) {
        // Linear scan over every stored word
        for (String w : words) {
            if (w.startsWith(prefix)) return true;
        }
        return false;
    }
}

Go:

import "strings"

type Trie struct {
	words map[string]bool
}

func Constructor() Trie {
	return Trie{words: map[string]bool{}}
}

func (this *Trie) Insert(word string) {
	this.words[word] = true
}

func (this *Trie) Search(word string) bool {
	return this.words[word]
}

func (this *Trie) StartsWith(prefix string) bool {
	// Linear scan over every stored word
	for w := range this.words {
		if strings.HasPrefix(w, prefix) {
			return true
		}
	}
	return false
}

JavaScript:

class Trie {
    constructor() {
        this.words = new Set();
    }

    /** @param {string} word @return {void} */
    insert(word) {
        this.words.add(word);
    }

    /** @param {string} word @return {boolean} */
    search(word) {
        return this.words.has(word);
    }

    /** @param {string} prefix @return {boolean} */
    startsWith(prefix) {
        // Linear scan over every stored word
        for (const w of this.words) {
            if (w.startsWith(prefix)) return true;
        }
        return false;
    }
}

C#:

using System;
using System.Collections.Generic;

public class Trie {
    private readonly HashSet<string> words = new HashSet<string>();

    public Trie() {
    }

    public void Insert(string word) {
        words.Add(word);
    }

    public bool Search(string word) {
        return words.Contains(word);
    }

    public bool StartsWith(string prefix) {
        // Linear scan; Ordinal avoids culture-sensitive string comparison
        foreach (string w in words) {
            if (w.StartsWith(prefix, StringComparison.Ordinal)) return true;
        }
        return false;
    }
}

C++:

#include <string>
#include <unordered_set>
using namespace std;

class Trie {
public:
    Trie() {}

    void insert(string word) {
        words.insert(word);
    }

    bool search(string word) {
        return words.count(word) > 0;
    }

    bool startsWith(string prefix) {
        // Linear scan over every stored word
        for (const string& w : words) {
            if (w.size() >= prefix.size() && w.compare(0, prefix.size(), prefix) == 0) {
                return true;
            }
        }
        return false;
    }

private:
    unordered_set<string> words;
};

Complexity Analysis

  • Time: insert and search are O(L) on average, where L is the string length (hashing reads every character). startsWith is O(N * L) in the worst case for N stored words.
  • Space: O(total characters inserted) for the stored strings.

Algorithm

Each trie node represents one prefix. It has a link for each possible next letter (26 for lowercase English) and a flag that says whether the prefix leading to it is itself a complete word. The root represents the empty prefix.

  1. insert(word): start at the root. For each character, follow its child link, creating a new node if the link is empty. After the last character, mark the node as the end of a word.
  2. A shared helper find(s) walks the same way but never creates nodes; it returns the node for s, or nothing if some link is missing.
  3. search(word): the node for word must exist and be marked as a word end.
  4. startsWith(prefix): the node for prefix only needs to exist, since every node lies on the path of some inserted word.

Python uses a dictionary for the children (idiomatic and compact); the other languages use a fixed array of 26 links indexed by ch - 'a'.

Implementation

Python:

class TrieNode:
    __slots__ = ("children", "is_end")

    def __init__(self):
        self.children = {}    # char -> TrieNode
        self.is_end = False   # True if the path to this node spells a word


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, s: str):
        # Follow existing links only; None means the path breaks off
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

Java:

class Trie {
    private static class Node {
        final Node[] children = new Node[26];
        boolean isEnd;   // true if the path to this node spells a word
    }

    private final Node root = new Node();

    public Trie() {
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (node.children[c] == null) {
                node.children[c] = new Node();
            }
            node = node.children[c];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Node node = find(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    // Follow existing links only; null means the path breaks off
    private Node find(String s) {
        Node node = root;
        for (int i = 0; i < s.length() && node != null; i++) {
            node = node.children[s.charAt(i) - 'a'];
        }
        return node;
    }
}

Go:

type trieNode struct {
	children [26]*trieNode
	isEnd    bool // true if the path to this node spells a word
}

type Trie struct {
	root *trieNode
}

func Constructor() Trie {
	return Trie{root: &trieNode{}}
}

func (this *Trie) Insert(word string) {
	node := this.root
	for i := 0; i < len(word); i++ {
		c := word[i] - 'a'
		if node.children[c] == nil {
			node.children[c] = &trieNode{}
		}
		node = node.children[c]
	}
	node.isEnd = true
}

func (this *Trie) Search(word string) bool {
	node := this.find(word)
	return node != nil && node.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
	return this.find(prefix) != nil
}

// find follows existing links only; nil means the path breaks off
func (this *Trie) find(s string) *trieNode {
	node := this.root
	for i := 0; i < len(s) && node != nil; i++ {
		node = node.children[s[i]-'a']
	}
	return node
}

JavaScript:

class TrieNode {
    constructor() {
        this.children = new Map(); // char -> TrieNode
        this.isEnd = false;        // true if the path to this node spells a word
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    /** @param {string} word @return {void} */
    insert(word) {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) {
                node.children.set(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    /** @param {string} word @return {boolean} */
    search(word) {
        const node = this.find(word);
        return node !== null && node.isEnd;
    }

    /** @param {string} prefix @return {boolean} */
    startsWith(prefix) {
        return this.find(prefix) !== null;
    }

    // Follow existing links only; null means the path breaks off
    find(s) {
        let node = this.root;
        for (const ch of s) {
            node = node.children.get(ch);
            if (node === undefined) return null;
        }
        return node;
    }
}

C#:

public class Trie {
    private class Node {
        public readonly Node[] Children = new Node[26];
        public bool IsEnd;   // true if the path to this node spells a word
    }

    private readonly Node root = new Node();

    public Trie() {
    }

    public void Insert(string word) {
        Node node = root;
        foreach (char ch in word) {
            int c = ch - 'a';
            if (node.Children[c] == null) {
                node.Children[c] = new Node();
            }
            node = node.Children[c];
        }
        node.IsEnd = true;
    }

    public bool Search(string word) {
        Node node = Find(word);
        return node != null && node.IsEnd;
    }

    public bool StartsWith(string prefix) {
        return Find(prefix) != null;
    }

    // Follow existing links only; null means the path breaks off
    private Node Find(string s) {
        Node node = root;
        for (int i = 0; i < s.Length && node != null; i++) {
            node = node.Children[s[i] - 'a'];
        }
        return node;
    }
}

C++:

#include <memory>
#include <string>
using namespace std;

class Trie {
public:
    Trie() : root(make_unique<Node>()) {}

    void insert(string word) {
        Node* node = root.get();
        for (char ch : word) {
            int c = ch - 'a';
            if (!node->children[c]) {
                node->children[c] = make_unique<Node>();
            }
            node = node->children[c].get();
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Node* node = find(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return find(prefix) != nullptr;
    }

private:
    struct Node {
        unique_ptr<Node> children[26];  // owned links, freed automatically
        bool isEnd = false;             // true if the path to this node spells a word
    };

    unique_ptr<Node> root;

    // Follow existing links only; nullptr means the path breaks off
    Node* find(const string& s) const {
        Node* node = root.get();
        for (size_t i = 0; i < s.size() && node != nullptr; i++) {
            node = node->children[s[i] - 'a'].get();
        }
        return node;
    }
};

Complexity Analysis

  • Time: O(L) for each insert, search and startsWith, where L is the length of the argument. Each character moves one link, and an array lookup or hash-map lookup on a single character is O(1).
  • Space: O(T) in total, where T is the number of characters across all inserted words: each insert creates at most L new nodes, and shared prefixes reuse nodes. With 26-slot arrays the constant factor is 26 pointers per node.

Key Insights

  1. A node is a prefix, not a letter. The letter lives on the link into the node; the node stands for the whole string spelled from the root.
  2. The end-of-word flag separates search from startsWith. Both walk the same path; only search also checks the flag.
  3. Shared prefixes are stored once. Inserting “car”, “cart” and “carton” uses 6 nodes below the root, not 13.
  4. Lookup time does not depend on how many words are stored. That is the advantage over the hash set, whose prefix query scans everything.
  5. Array vs map children. A 26-slot array gives the fastest lookups for a small fixed alphabet; a hash map uses less memory for sparse nodes or large alphabets (Unicode).

Edge Cases

  • Searching a strict prefix of a stored word: search("car") after only insert("cart") must be false.
  • A word that extends a stored word: search("dogs") after insert("dog") is false; the walk runs out of links.
  • Prefix equal to a whole word: startsWith("dog") after insert("dog") is true.
  • Inserting the same word twice: the second insert creates nothing and only re-sets the flag.
  • Inserting a prefix after a longer word: insert("car") after insert("cart") must just set the flag on an existing node.
  • Long words (2000 characters): the iterative walk has no recursion depth to worry about.

Common Mistakes

  1. Returning true from search when the path exists. Without checking isEnd, prefixes are reported as words.
  2. Creating nodes during search or startsWith. Lookups must not modify the trie; use a separate non-creating find.
  3. Marking the end flag on the wrong node. The flag goes on the node reached after the last character, not on its parent.
  4. Culture-sensitive comparisons. In C#, string.StartsWith(string) without StringComparison.Ordinal uses the current culture; use ordinal for exact character matching.
  5. Leaking nodes in C++. Raw new without a destructor leaks the whole tree; unique_ptr children free it automatically.

Interview Tips

  1. Draw a small trie for three words that share a prefix before writing code; it makes the node/flag distinction obvious.
  2. Write the shared find helper first; search and startsWith then become one-liners.
  3. Ask about the alphabet. Lowercase letters justify an array of 26; arbitrary characters call for a hash map.
  4. State the per-operation cost in terms of the word length, and contrast it with the hash-set baseline’s O(N * L) prefix scan.
  5. Expect a follow-up such as wildcard search, deletion, or counting words with a prefix.

Follow-up Questions

  1. How would you support delete(word)? Clear the end flag, then walk back up removing nodes that have no children and no end flag. Keeping a child count per node makes the check O(1).
  2. How would you count the words that start with a prefix? Keep a counter on each node that is incremented on every insert passing through it; the answer is the counter at the prefix’s node.
  3. How would you return autocomplete suggestions? Walk to the prefix’s node, then run a DFS from it to collect words, optionally keeping the top results by frequency at each node.
  4. What if the search pattern can contain a wildcard? Branch into every child at a wildcard position; see Design Add and Search Words Data Structure.
  5. How can you reduce memory? Use a compressed (radix) trie that merges chains of single-child nodes, or a hash map per node instead of a fixed array.