Implement Trie (Prefix Tree)

Problem Statement

Implement a Trie (also called prefix tree) with the following operations:

• insert(word) — Insert a word into the trie.
• search(word) — Search for an exact word in the trie and return whether it exists.
• startsWith(prefix) — Return whether there is any word in the trie that starts with the given prefix.

What to notice first

• A Trie efficiently stores and retrieves strings by their prefixes.
• Each node can have up to 26 children (for lowercase English letters).
• The key insight is: a prefix doesn’t need to be a complete word.
• Both search and startsWith traverse the same path, differing only in their end-of-word check.

Examples

Operation	Input	Output	Notes
Insert	"apple"	—	Tree now has path: a→p→p→l→e
Search	"apple"	true	Complete word exists
Search	"app"	false	Prefix exists but not marked as word
StartsWith	"app"	true	Prefix exists in tree
Insert	"app"	—	Now search(“app”) returns true

Constraints

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 × 10^4 calls will be made to insert, search, and startsWith.

Real-World Applications

Where this pattern appears

• Autocomplete systems — quickly find all words with a given prefix.
• Spell checkers — validate words and suggest corrections by prefix.
• IP routing tables — organize network prefixes for fast packet routing.
• Dictionary compression — efficiently store and retrieve large word lists.
• Search engine indexing — prefix matching for search suggestions.

Complexity Comparison

Approach	Insert	Search	StartsWith	Space
Recursive	O(m)	O(m)	O(m)	O(m × 26)
Iterative	O(m)	O(m)	O(m)	O(m × 26)

m = length of word/prefix, space = nodes × alphabet size

Which approach should you learn first?

• Pick Iterative for clarity and interviews — easier to explain and debug.
• Pick Recursive if you want to practice the recursive tree traversal pattern.

Most Clear

Iterative

O(m) time · O(m×26) space

Pattern Practice

Recursive

O(m) time · O(m×26) space

Approach 1: Iterative (Recommended)

★ Recommended

Build a tree of nodes where each node represents a character. For each operation, iterate through the characters, creating new nodes as needed during insertion. For search and prefix matching, follow the existing path and return whether it reaches the target or beyond.

⏱ Time O(m) Single pass per word 💾 Space O(m×26) Trie nodes storage

Step-by-step Example

Insert “cat”:

Insert 'c': root → c (new node)
Insert 'a': c → a (new node)
Insert 't': a → t (new node, mark as end-of-word)

Search “cat”:

Follow 'c' → 'a' → 't' → found and marked as end-of-word → return true

Search “ca”:

Follow 'c' → 'a' → path exists but NOT marked as end-of-word → return false

StartsWith “ca”:

Follow 'c' → 'a' → path exists → return true (doesn't care about end-of-word)

Pseudocode

class TrieNode:
    children = {}
    is_end_of_word = False

class Trie:
    root = TrieNode()

    function insert(word):
        node = root
        for each char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    function search(word):
        node = root
        for each char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    function startsWith(prefix):
        node = root
        for each char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Solution Code

Python

implement_trie_iterative.py

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


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

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

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True


# Example usage
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))    # True
print(trie.search("app"))      # False
print(trie.startsWith("app"))  # True
trie.insert("app")
print(trie.search("app"))      # True

C++

implement_trie_iterative.cpp

#include <iostream>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool is_end_of_word = false;
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->is_end_of_word = true;
    }

    bool search(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return node->is_end_of_word;
    }

    bool startsWith(const std::string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    std::cout << trie.search("apple") << std::endl;    // 1
    std::cout << trie.search("app") << std::endl;      // 0
    std::cout << trie.startsWith("app") << std::endl;  // 1
    return 0;
}

Java

ImplementTrie_Iterative.java

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return false;
            }
            node = node.children.get(c);
        }
        return node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return false;
            }
            node = node.children.get(c);
        }
        return true;
    }
}

public class ImplementTrie_Iterative {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));    // true
        System.out.println(trie.search("app"));      // false
        System.out.println(trie.startsWith("app"));  // true
        trie.insert("app");
        System.out.println(trie.search("app"));      // true
    }
}

JavaScript

implement_trie_iterative.js

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

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

    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!(char in node.children)) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!(char in node.children)) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!(char in node.children)) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));    // true
console.log(trie.search("app"));      // false
console.log(trie.startsWith("app"));  // true
trie.insert("app");
console.log(trie.search("app"));      // true

Rust

implement_trie_iterative.rs

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Default)]
struct TrieNode {
    children: HashMap<char, Rc<RefCell<TrieNode>>>,
    is_end_of_word: bool,
}

struct Trie {
    root: Rc<RefCell<TrieNode>>,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: Rc::new(RefCell::new(TrieNode::default())),
        }
    }

    fn insert(&self, word: String) {
        let mut node = Rc::clone(&self.root);
        for ch in word.chars() {
            let mut node_ref = node.borrow_mut();
            node = Rc::clone(
                node_ref
                    .children
                    .entry(ch)
                    .or_insert_with(|| Rc::new(RefCell::new(TrieNode::default()))),
            );
        }
        node.borrow_mut().is_end_of_word = true;
    }

    fn search(&self, word: String) -> bool {
        let mut node = Rc::clone(&self.root);
        for ch in word.chars() {
            let node_ref = node.borrow();
            if let Some(child) = node_ref.children.get(&ch) {
                node = Rc::clone(child);
            } else {
                return false;
            }
        }
        node.borrow().is_end_of_word
    }

    fn starts_with(&self, prefix: String) -> bool {
        let mut node = Rc::clone(&self.root);
        for ch in prefix.chars() {
            let node_ref = node.borrow();
            if let Some(child) = node_ref.children.get(&ch) {
                node = Rc::clone(child);
            } else {
                return false;
            }
        }
        true
    }
}

fn main() {
    let trie = Trie::new();
    trie.insert("apple".to_string());
    println!("{}", trie.search("apple".to_string()));    // true
    println!("{}", trie.search("app".to_string()));      // false
    println!("{}", trie.starts_with("app".to_string())); // true
    trie.insert("app".to_string());
    println!("{}", trie.search("app".to_string()));      // true
}

Go

implement_trie_iterative.go

package main

import "fmt"

type TrieNode struct {
  children    map[rune]*TrieNode
  isEndOfWord bool
}

type Trie struct {
  root *TrieNode
}

func NewTrie() *Trie {
  return &Trie{
    root: &TrieNode{
      children: make(map[rune]*TrieNode),
    },
  }
}

func (t *Trie) Insert(word string) {
  node := t.root
  for _, ch := range word {
    if _, exists := node.children[ch]; !exists {
      node.children[ch] = &TrieNode{
        children: make(map[rune]*TrieNode),
      }
    }
    node = node.children[ch]
  }
  node.isEndOfWord = true
}

func (t *Trie) Search(word string) bool {
  node := t.root
  for _, ch := range word {
    if child, exists := node.children[ch]; exists {
      node = child
    } else {
      return false
    }
  }
  return node.isEndOfWord
}

func (t *Trie) StartsWith(prefix string) bool {
  node := t.root
  for _, ch := range prefix {
    if child, exists := node.children[ch]; exists {
      node = child
    } else {
      return false
    }
  }
  return true
}

func main() {
  trie := NewTrie()
  trie.Insert("apple")
  fmt.Println(trie.Search("apple"))    // true
  fmt.Println(trie.Search("app"))      // false
  fmt.Println(trie.StartsWith("app"))  // true
  trie.Insert("app")
  fmt.Println(trie.Search("app"))      // true
}

Approach 2: Helper Method (Recursive Pattern)

🎯 Interview Favourite

Extract a helper method findNode(prefix) that recursively (or iteratively in the helper) searches for a node. Then search checks the end-of-word flag and startsWith only checks node existence. This reduces code duplication.

⏱ Time O(m) Single traversal 💾 Space O(m) Call stack + nodes

Solution Code

Python

implement_trie_recursive.py

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


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

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

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

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

    def _find_node(self, prefix: str) -> TrieNode:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node


# Example usage
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))  # True
print(trie.search("app"))    # False
print(trie.startsWith("app"))  # True

C++

implement_trie_recursive.cpp

#include <iostream>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool is_end_of_word = false;
};

class Trie {
private:
    TrieNode* root;
    TrieNode* findNode(const std::string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return nullptr;
            }
            node = node->children[c];
        }
        return node;
    }

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->is_end_of_word = true;
    }

    bool search(const std::string& word) {
        TrieNode* node = findNode(word);
        return node != nullptr && node->is_end_of_word;
    }

    bool startsWith(const std::string& prefix) {
        return findNode(prefix) != nullptr;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    std::cout << trie.search("apple") << std::endl;   // 1
    std::cout << trie.search("app") << std::endl;     // 0
    std::cout << trie.startsWith("app") << std::endl; // 1
    return 0;
}

Java

ImplementTrie_Recursive.java

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEndOfWord;
    }

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

    private TrieNode findNode(String str) {
        TrieNode node = root;
        for (char c : str.toCharArray()) {
            if (!node.children.containsKey(c)) {
                return null;
            }
            node = node.children.get(c);
        }
        return node;
    }
}

public class ImplementTrie_Recursive {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));    // true
        System.out.println(trie.search("app"));      // false
        System.out.println(trie.startsWith("app"));  // true
    }
}

JavaScript

implement_trie_recursive.js

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

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

    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!(char in node.children)) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    search(word) {
        let node = this.findNode(word);
        return node !== null && node.isEndOfWord;
    }

    startsWith(prefix) {
        return this.findNode(prefix) !== null;
    }

    findNode(str) {
        let node = this.root;
        for (let char of str) {
            if (!(char in node.children)) {
                return null;
            }
            node = node.children[char];
        }
        return node;
    }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));    // true
console.log(trie.search("app"));      // false
console.log(trie.startsWith("app"));  // true

Rust

implement_trie_recursive.rs

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Default)]
struct TrieNode {
    children: HashMap<char, Rc<RefCell<TrieNode>>>,
    is_end_of_word: bool,
}

struct Trie {
    root: Rc<RefCell<TrieNode>>,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: Rc::new(RefCell::new(TrieNode::default())),
        }
    }

    fn insert(&self, word: String) {
        let mut node = Rc::clone(&self.root);
        for ch in word.chars() {
            let mut node_ref = node.borrow_mut();
            node = Rc::clone(
                node_ref
                    .children
                    .entry(ch)
                    .or_insert_with(|| Rc::new(RefCell::new(TrieNode::default()))),
            );
        }
        node.borrow_mut().is_end_of_word = true;
    }

    fn search(&self, word: String) -> bool {
        if let Some(node) = self.find_node(word) {
            node.borrow().is_end_of_word
        } else {
            false
        }
    }

    fn starts_with(&self, prefix: String) -> bool {
        self.find_node(prefix).is_some()
    }

    fn find_node(&self, prefix: String) -> Option<Rc<RefCell<TrieNode>>> {
        let mut node = Rc::clone(&self.root);
        for ch in prefix.chars() {
            let node_ref = node.borrow();
            if let Some(child) = node_ref.children.get(&ch) {
                node = Rc::clone(child);
            } else {
                return None;
            }
        }
        Some(node)
    }
}

fn main() {
    let trie = Trie::new();
    trie.insert("apple".to_string());
    println!("{}", trie.search("apple".to_string()));    // true
    println!("{}", trie.search("app".to_string()));      // false
    println!("{}", trie.starts_with("app".to_string())); // true
}

Go

implement_trie_recursive.go

package main

import "fmt"

type TrieNode struct {
  children    map[rune]*TrieNode
  isEndOfWord bool
}

type Trie struct {
  root *TrieNode
}

func NewTrie() *Trie {
  return &Trie{
    root: &TrieNode{
      children: make(map[rune]*TrieNode),
    },
  }
}

func (t *Trie) Insert(word string) {
  node := t.root
  for _, ch := range word {
    if _, exists := node.children[ch]; !exists {
      node.children[ch] = &TrieNode{
        children: make(map[rune]*TrieNode),
      }
    }
    node = node.children[ch]
  }
  node.isEndOfWord = true
}

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

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

func (t *Trie) findNode(prefix string) *TrieNode {
  node := t.root
  for _, ch := range prefix {
    if child, exists := node.children[ch]; exists {
      node = child
    } else {
      return nil
    }
  }
  return node
}

func main() {
  trie := NewTrie()
  trie.Insert("apple")
  fmt.Println(trie.Search("apple"))    // true
  fmt.Println(trie.Search("app"))      // false
  fmt.Println(trie.StartsWith("app"))  // true
}

Common mistakes

Watch for these pitfalls

• Forgetting to mark the last node as is_end_of_word during insertion.
• Returning True in search when the path exists but the word is not complete.
• Mixing up search (must be exact word) and startsWith (prefix only).
• In languages like Java, forgetting to initialize the HashMap in each node.
• Off-by-one errors when iterating through characters.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

implement_trie_prefix_tree_space_optimized.py

"""
Solution for Implement Trie (Prefix Tree)
"""

def solve():
    """Implementation for approach 3 of Implement Trie (Prefix Tree)"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

implement_trie_prefix_tree_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Implement Trie (Prefix Tree)
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ImplementTriePrefixTreeSpaceOptimized.java

/**
 * Solution for Implement Trie (Prefix Tree)
 * Approach 3
 */
public class ImplementTriePrefixTreeSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

implement_trie_prefix_tree_space_optimized.js

/**
 * Solution for Implement Trie (Prefix Tree)
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

implement_trie_prefix_tree_space_optimized.rs

/// Solution for Implement Trie (Prefix Tree)
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

implement_trie_prefix_tree_space_optimized.go

package main

import "fmt"

// Solution for Implement Trie (Prefix Tree)
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Design Add and Search Words Data Structure ↗ Medium #211
• Word Search II ↗ Hard #212
• Longest Common Prefix ↗ Easy #14
• Longest Word in Dictionary ↗ Easy #720

Interview Tips

Key trade-offs to discuss

• Iterative vs. Recursive: Iterative is clearer and avoids stack overflow; recursive uses helper methods to reduce duplication.
• Space optimization: Using arrays instead of HashMaps for children (fixed size 26) saves space at the cost of memory per node.
• Extensions: Discuss how to add deletion, counting words, or returning all words with a prefix.
• Follow-up: How would you handle non-English characters? (Use larger alphabet or Unicode maps instead of fixed 26.)
• Edge cases: Empty strings, single character words, and duplicate inserts.

← Previous
#207 Course Schedule II Next
#209 Minimum Size Subarray Sum →