208. Implement Trie (Prefix Tree) (Medium)

Problem

Implement a trie with the following methods:

insert(word)
search(word), true iff the exact word has been inserted.
startsWith(prefix), true iff some inserted word starts with prefix.

Example

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");    // true
trie.search("app");      // false
trie.startsWith("app");  // true
trie.insert("app");
trie.search("app");      // true

LeetCode 208 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, hash set of words, linear prefix check

insert adds the word to a set; startsWith scans the set.

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

    def insert(self, word):
        self.words.add(word)           # L1: O(L) hash + store

    def search(self, word):
        return word in self.words      # L2: O(L) hash lookup

    def startsWith(self, prefix):
        return any(w.startswith(prefix) for w in self.words)  # L3: O(W · L) scan

class Trie {
    private words: Set<string> = new Set();

    insert(word: string): void {
        this.words.add(word);            // L1: O(L) hash + store
    }

    search(word: string): boolean {
        return this.words.has(word);     // L2: O(L) hash lookup
    }

    startsWith(prefix: string): boolean {
        for (const w of this.words) {
            if (w.startsWith(prefix)) return true;  // L3: O(W · L) scan
        }
        return false;
    }
}

package main

import "fmt"

type Trie struct {
    words map[string]bool
}

func NewTrie() *Trie { return &Trie{words: make(map[string]bool)} }

func (t *Trie) Insert(word string) {
    t.words[word] = true               // L1: O(L) hash + store
}

func (t *Trie) Search(word string) bool {
    return t.words[word]               // L2: O(L) hash lookup
}

func (t *Trie) StartsWith(prefix string) bool {
    for w := range t.words {
        if len(w) >= len(prefix) && w[:len(prefix)] == prefix { // L3: O(W · L) scan
            return true
        }
    }
    return false
}

func runTests() {
    t := NewTrie()
    t.Insert("apple")
    fmt.Println(t.Search("apple"), t.Search("app"), t.StartsWith("app"))
}

func main() { runTests() }

final class Trie {
    private var words: Set<String> = []
    init() {}
    func insert(_ word: String) { words.insert(word) }
    func search(_ word: String) -> Bool { words.contains(word) }
    func startsWith(_ prefix: String) -> Bool { words.contains { $0.hasPrefix(prefix) } }
}

Where the time goes, line by line

Variables: L = length of the word/prefix, W = total number of words stored.

Line	Per-call cost	Times executed	Contribution
L1 (insert)	$O(L)$	1	$O(L)$ per insert
L2 (search)	$O(L)$	1	$O(L)$ per search
L3 (startsWith scan)	$O(L)$	W	$O(W · L)$ per startsWith ← dominates

insert and search are fast because set hashing is $O(L)$ (must hash the string). startsWith is slow because it must check every stored word.

Complexity

insert, search: $O(L)$ average.
startsWith: $O(W · L)$ where W = total words, L = prefix length.

Fails when there are many words, the whole point of a trie is to make startsWith independent of W.

Approach 2: Trie with hash-map children (canonical)

Each node has a dict of children and a boolean “is end of word.”

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for ch in word:                      # L1: iterate over L characters
            if ch not in node.children:
                node.children[ch] = TrieNode()  # L2: O(1) create node
            node = node.children[ch]         # L3: O(1) descend
        node.is_end = True                   # L4: O(1) mark end

    def search(self, word):
        node = self._walk(word)              # L5: O(L) walk
        return node is not None and node.is_end  # L6: O(1) check

    def startsWith(self, prefix):
        return self._walk(prefix) is not None  # L7: O(L) walk

    def _walk(self, s):
        node = self.root
        for ch in s:                         # L8: iterate over L characters
            if ch not in node.children:      # L9: O(1) dict lookup
                return None
            node = node.children[ch]         # L10: O(1) descend
        return node

class TrieNode {
    children: Map<string, TrieNode> = new Map();
    isEnd: boolean = false;
}

class Trie {
    private root = new TrieNode();

    insert(word: string): void {
        let node = this.root;
        for (const ch of word) {                    // L1: iterate over L characters
            if (!node.children.has(ch))
                node.children.set(ch, new TrieNode()); // L2: O(1) create node
            node = node.children.get(ch)!;          // L3: O(1) descend
        }
        node.isEnd = true;                          // L4: O(1) mark end
    }

    search(word: string): boolean {
        const node = this._walk(word);              // L5: O(L) walk
        return node !== null && node.isEnd;         // L6: O(1) check
    }

    startsWith(prefix: string): boolean {
        return this._walk(prefix) !== null;         // L7: O(L) walk
    }

    private _walk(s: string): TrieNode | null {
        let node = this.root;
        for (const ch of s) {                      // L8: iterate over L characters
            if (!node.children.has(ch))             // L9: O(1) map lookup
                return null;
            node = node.children.get(ch)!;          // L10: O(1) descend
        }
        return node;
    }
}

package main

import "fmt"

type TrieNode struct {
    Children [26]*TrieNode
    IsEnd    bool
}

type Trie struct{ Root *TrieNode }

func NewTrie() *Trie { return &Trie{Root: &TrieNode{}} }

func (t *Trie) Insert(word string) {
    node := t.Root
    for _, ch := range word {               // L1: iterate over L characters
        i := ch - 'a'
        if node.Children[i] == nil {
            node.Children[i] = &TrieNode{} // L2: O(1) create node
        }
        node = node.Children[i]            // L3: O(1) descend
    }
    node.IsEnd = true                      // L4: O(1) mark end
}

func (t *Trie) Search(word string) bool {
    node := t.walk(word)                   // L5: O(L) walk
    return node != nil && node.IsEnd       // L6: O(1) check
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.walk(prefix) != nil           // L7: O(L) walk
}

func (t *Trie) walk(s string) *TrieNode {
    node := t.Root
    for _, ch := range s {                 // L8: iterate over L characters
        i := ch - 'a'
        if node.Children[i] == nil {       // L9: O(1) array lookup
            return nil
        }
        node = node.Children[i]            // L10: O(1) descend
    }
    return node
}

func assert(condition bool, msgs ...string) {
    if !condition {
        msg := "assertion failed"
        if len(msgs) > 0 { msg = msgs[0] }
        panic(msg)
    }
}

func runTests() {
    t := NewTrie()
    t.Insert("apple")
    assert(t.Search("apple") == true)
    assert(t.Search("app") == false)
    assert(t.StartsWith("app") == true)
    t.Insert("app")
    assert(t.Search("app") == true)
    assert(t.StartsWith("b") == false)
    fmt.Println("all tests pass")
}

func main() { runTests() }

final class Trie {
    private let root = TrieNode()
    init() {}
    func insert(_ word: String) {
        var node = root
        for character in word {
            if node.children[character] == nil { node.children[character] = TrieNode() }
            guard let child = node.children[character] else { return }
            node = child
        }
        node.isWord = true
    }
    func search(_ word: String) -> Bool { node(for: word)?.isWord == true }
    func startsWith(_ prefix: String) -> Bool { node(for: prefix) != nil }
    private func node(for text: String) -> TrieNode? {
        var node = root
        for character in text {
            guard let child = node.children[character] else { return nil }
            node = child
        }
        return node
    }
}

Where the time goes, line by line

Variables: L = length of the word/prefix.

Line	Per-call cost	Times executed	Contribution
L1-L4 (insert loop)	$O(1)$ per char	L	$O(L)$ per insert ← dominates for insert
L8-L10 (_walk loop)	$O(1)$ per char	L	$O(L)$ per search/startsWith ← dominates for queries
L5/L6/L7 (search/startsWith)	$O(L)$ + $O(1)$	1	$O(L)$

Each method is dominated by the loop over the word/prefix characters. Hash-map child lookup (L9) is $O(1)$ average.

Complexity

insert, search, startsWith: $O(L)$ each.
Space: $O(total characters inserted)$ .

Works for arbitrary alphabets.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Array of 26 children (tighter for lowercase-only)

Replace the dict with a fixed 26-element array.

class TrieNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = [None] * 26     # L1: O(26) = O(1) allocation per node
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for ch in word:                  # L2: iterate over L characters
            i = ord(ch) - ord('a')      # L3: O(1) index computation
            if node.children[i] is None:
                node.children[i] = TrieNode()  # L4: O(1) create node
            node = node.children[i]     # L5: O(1) descend
        node.is_end = True

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for ch in s:                     # L6: iterate over L characters
            i = ord(ch) - ord('a')      # L7: O(1) index
            if node.children[i] is None:
                return None
            node = node.children[i]     # L8: O(1) descend
        return node

class TrieNode {
    children: (TrieNode | null)[] = new Array(26).fill(null); // L1: O(1) allocation
    isEnd: boolean = false;
}

class Trie {
    private root = new TrieNode();

    insert(word: string): void {
        let node = this.root;
        for (const ch of word) {                  // L2: iterate over L characters
            const i = ch.charCodeAt(0) - 97;     // L3: O(1) index computation
            if (!node.children[i])
                node.children[i] = new TrieNode(); // L4: O(1) create node
            node = node.children[i]!;             // L5: O(1) descend
        }
        node.isEnd = true;
    }

    search(word: string): boolean {
        const node = this._walk(word);
        return node !== null && node.isEnd;
    }

    startsWith(prefix: string): boolean {
        return this._walk(prefix) !== null;
    }

    private _walk(s: string): TrieNode | null {
        let node = this.root;
        for (const ch of s) {                    // L6: iterate over L characters
            const i = ch.charCodeAt(0) - 97;     // L7: O(1) index
            if (!node.children[i]) return null;
            node = node.children[i]!;             // L8: O(1) descend
        }
        return node;
    }
}

package main

import "fmt"

// Go's [26]*TrieNode is already the array approach -- this is the canonical Go form.

type TrieNode struct {
    Children [26]*TrieNode            // L1: O(1) allocation (26 pointers)
    IsEnd    bool
}

type Trie struct{ Root *TrieNode }

func NewTrie() *Trie { return &Trie{Root: &TrieNode{}} }

func (t *Trie) Insert(word string) {
    node := t.Root
    for _, ch := range word {        // L2: iterate over L characters
        i := ch - 'a'               // L3: O(1) index computation
        if node.Children[i] == nil {
            node.Children[i] = &TrieNode{} // L4: O(1) create node
        }
        node = node.Children[i]    // L5: O(1) descend
    }
    node.IsEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.walk(word)
    return node != nil && node.IsEnd
}

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

func (t *Trie) walk(s string) *TrieNode {
    node := t.Root
    for _, ch := range s {          // L6: iterate over L characters
        i := ch - 'a'              // L7: O(1) index
        if node.Children[i] == nil {
            return nil
        }
        node = node.Children[i]    // L8: O(1) descend
    }
    return node
}

func assert(condition bool, msgs ...string) {
    if !condition {
        msg := "assertion failed"
        if len(msgs) > 0 { msg = msgs[0] }
        panic(msg)
    }
}

func runTests() {
    t := NewTrie()
    t.Insert("apple")
    assert(t.Search("apple") == true)
    assert(t.Search("app") == false)
    assert(t.StartsWith("app") == true)
    t.Insert("app")
    assert(t.Search("app") == true)
    assert(t.StartsWith("b") == false)
    fmt.Println("all tests pass")
}

func main() { runTests() }

private final class ArrayTrieNode {
    var children = Array<ArrayTrieNode?>(repeating: nil, count: 26)
    var isWord = false
}

final class Trie {
    private let root = ArrayTrieNode()
    init() {}
    func insert(_ word: String) {
        var node = root
        for character in word {
            guard let index = index(of: character) else { return }
            if node.children[index] == nil { node.children[index] = ArrayTrieNode() }
            guard let child = node.children[index] else { return }
            node = child
        }
        node.isWord = true
    }
    func search(_ word: String) -> Bool { node(for: word)?.isWord == true }
    func startsWith(_ prefix: String) -> Bool { node(for: prefix) != nil }
    private func node(for text: String) -> ArrayTrieNode? {
        var node = root
        for character in text {
            guard let index = index(of: character), let child = node.children[index] else { return nil }
            node = child
        }
        return node
    }
    private func index(of character: Character) -> Int? {
        guard let ascii = character.asciiValue, ascii >= 97, ascii <= 122 else { return nil }
        return Int(ascii - 97)
    }
}

Where the time goes, line by line

Variables: L = length of the word/prefix.

Line	Per-call cost	Times executed	Contribution
L1 (node init)	$O(1)$ (26 slots)	per new node	$O(1)$ per node
L2-L5 (insert loop)	$O(1)$ per char	L	$O(L)$ per insert ← dominates for insert
L6-L8 (_walk loop)	$O(1)$ per char	L	$O(L)$ per query ← dominates for queries

The 26-slot array replaces dict lookup (L9 in Approach 2) with direct index access (L7). Both are $O(1)$ , but the array version has smaller constant factors and better cache behavior.

Complexity

Same $O(L)$ operations.
Space: $O(26 · nodes)$ . Can exceed the hash-map approach if the trie is sparse.

Slightly faster constant factors; restricted to lowercase. Use when the problem guarantees a fixed small alphabet.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	insert	search	startsWith	Space
Hash set of words	$O(1)$	$O(1)$	$O(W · L)$	$O(total chars)$
Trie with hash children	$O(L)$	$O(L)$	$O(L)$	$O(total chars)$
Trie with 26-array children	$O(L)$	$O(L)$	$O(L)$	$O(26 · nodes)$

The hash-children trie is the canonical interview implementation and the building block for problems 211 and 212.

Test cases

# Quick smoke tests - paste into a REPL or save as test_208.py and run.
# Uses the canonical Approach 2 implementation (hash-map children).

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def insert(self, word):
        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):
        node = self._walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

def _run_tests():
    trie = Trie()
    trie.insert("apple")
    assert trie.search("apple") == True
    assert trie.search("app") == False      # not inserted, only prefix
    assert trie.startsWith("app") == True
    trie.insert("app")
    assert trie.search("app") == True
    assert trie.search("ap") == False       # only prefix, not word
    assert trie.startsWith("b") == False    # no words with prefix "b"
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

class TrieNode {
    children: Map<string, TrieNode> = new Map();
    isEnd: boolean = false;
}

class Trie {
    private root = new TrieNode();
    insert(word: string): void {
        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;
    }
    search(word: string): boolean {
        const node = this._walk(word);
        return node !== null && node.isEnd;
    }
    startsWith(prefix: string): boolean {
        return this._walk(prefix) !== null;
    }
    private _walk(s: string): TrieNode | null {
        let node = this.root;
        for (const ch of s) {
            if (!node.children.has(ch)) return null;
            node = node.children.get(ch)!;
        }
        return node;
    }
}

const trie = new Trie();
trie.insert("apple");
console.assert(trie.search("apple") === true);
console.assert(trie.search("app") === false);
console.assert(trie.startsWith("app") === true);
trie.insert("app");
console.assert(trie.search("app") === true);
console.assert(trie.search("ap") === false);
console.assert(trie.startsWith("b") === false);
console.log("all tests pass");

package main

import "fmt"

type TrieNode struct {
    Children [26]*TrieNode
    IsEnd    bool
}

type Trie struct{ Root *TrieNode }

func NewTrie() *Trie { return &Trie{Root: &TrieNode{}} }

func (t *Trie) Insert(word string) {
    node := t.Root
    for _, ch := range word {
        i := ch - 'a'
        if node.Children[i] == nil { node.Children[i] = &TrieNode{} }
        node = node.Children[i]
    }
    node.IsEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.walk(word)
    return node != nil && node.IsEnd
}

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

func (t *Trie) walk(s string) *TrieNode {
    node := t.Root
    for _, ch := range s {
        i := ch - 'a'
        if node.Children[i] == nil { return nil }
        node = node.Children[i]
    }
    return node
}

func assert(condition bool, msgs ...string) {
    if !condition {
        msg := "assertion failed"
        if len(msgs) > 0 { msg = msgs[0] }
        panic(msg)
    }
}

func runTests() {
    trie := NewTrie()
    trie.Insert("apple")
    assert(trie.Search("apple") == true)
    assert(trie.Search("app") == false)     // not inserted, only prefix
    assert(trie.StartsWith("app") == true)
    trie.Insert("app")
    assert(trie.Search("app") == true)
    assert(trie.Search("ap") == false)      // only prefix, not word
    assert(trie.StartsWith("b") == false)   // no words with prefix "b"
    fmt.Println("all tests pass")
}

func main() { runTests() }

Tries, prefix tree implementation

Trie Prefix Search, the prefix tree model for sharing string prefixes and pruning searches.
Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.

208. Implement Trie (Prefix Tree) (Medium)

Problem

Try it yourself

Approach 1: Brute force, hash set of words, linear prefix check

Approach 2: Trie with hash-map children (canonical)

Approach 3: Array of 26 children (tighter for lowercase-only)

Summary

Test cases

Related data structures

Related concepts