208. Implement Trie Prefix Tree - Explanation

Description

A prefix tree (also known as a trie) is a tree data structure used to efficiently store and retrieve keys in a set of strings. Some applications of this data structure include auto-complete and spell checker systems.

Implement the PrefixTree class:

PrefixTree() Initializes the prefix tree object.
void insert(String word) Inserts the string word into the prefix tree.
boolean search(String word) Returns true if the string word is in the prefix tree (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input:
["Trie", "insert", "dog", "search", "dog", "search", "do", "startsWith", "do", "insert", "do", "search", "do"]

Output:
[null, null, true, false, true, null, true]

Explanation:
PrefixTree prefixTree = new PrefixTree();
prefixTree.insert("dog");
prefixTree.search("dog");    // return true
prefixTree.search("do");     // return false
prefixTree.startsWith("do"); // return true
prefixTree.insert("do");
prefixTree.search("do");     // return true

Constraints:

1 <= word.length, prefix.length <= 1000
word and prefix are made up of lowercase English letters.

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time for each function call and O(t) space, where n is the length of the given string and t is the total number of nodes created in the Trie.

Hint 1

A Trie is structured as a tree-like data structure where each node contains a hash map (or an array for fixed character sets) to store references to its child nodes, which represent characters. Each node also includes a boolean flag to indicate whether the current node marks the end of a valid word. The Trie starts with a root node that does not hold any character and serves as the entry point for all operations. The child nodes of the root and subsequent nodes represent unique characters from the words stored in the Trie, forming a hierarchical structure based on the prefixes of the words.

Hint 2

To insert a word, we iterate through the characters of the word with index i, starting at the root of the Trie as the current node. If the current node already contains word[i], we continue to the next character and move to the node that word[i] points to. If word[i] is not present, we create a new node for word[i] and continue the process until we reach the end of the word. We mark the boolean variable as true as it is the end of the inserted word.

Hint 3

Searching for a word is similar to inserting, but instead of creating new nodes, we return false if we don't find a character in the path while iterating or if the end-of-word marker is not set to true when we reach the end of the word.

Company Tags

MongoDB5 Microsoft4 Apple2 Google8 Amazon6 General Motors4 Meta3 Roblox2 DocuSign2 Bloomberg11 DoorDash11 Adobe3 Tiktok3 Uber3 Citadel3 Snowflake3 Grammarly3 Oracle2 Walmart Labs2

Prerequisites

Before attempting this problem, you should be comfortable with:

Tree Data Structures - Understanding parent-child relationships and tree traversal
Hash Maps / Arrays for Children - Storing and accessing child nodes efficiently
String Processing - Character-by-character iteration and ASCII manipulation
Object-Oriented Design - Creating classes with methods that maintain internal state

1. Prefix Tree (Array)

Intuition

A Prefix Tree (Trie) is a tree-like data structure designed for fast string operations.

Each node represents a character, and paths from the root represent words.

Common prefixes are shared, which saves space.
Each node has 26 children (for letters a-z), indexed directly using character positions.
A boolean flag endOfWord tells us whether a complete word ends at that node.

Why Trie is useful:

Searching words and prefixes is O(length of word), not dependent on how many words exist.
Ideal for problems involving dictionary lookups, autocomplete, and prefix checks.

Algorithm

Data Structure

Each node contains:
- children[26]: array of child pointers (one for each letter)
- endOfWord: marks completion of a word

Insert(word)

Start from the root.
For each character in the word:
- Convert character to index (c - 'a')
- If the child node doesn’t exist, create it.
- Move to the child.
After processing all characters, mark endOfWord = true.

Search(word)

Start from the root.
For each character:
- Move to the corresponding child.
- If missing, return false.
After traversal:
- Return true only if endOfWord is true.

StartsWith(prefix)

Start from the root.
Traverse characters of the prefix.
If all characters exist in sequence, return true.
No need to check endOfWord.

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.endOfWord = False

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

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            i = ord(c) - ord("a")
            if cur.children[i] == None:
                cur.children[i] = TrieNode()
            cur = cur.children[i]
        cur.endOfWord = True

    def search(self, word: str) -> bool:
        cur = self.root
        for c in word:
            i = ord(c) - ord("a")
            if cur.children[i] == None:
                return False
            cur = cur.children[i]
        return cur.endOfWord

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for c in prefix:
            i = ord(c) - ord("a")
            if cur.children[i] == None:
                return False
            cur = cur.children[i]
        return True

public class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean endOfWord = false;
}

public class PrefixTree {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) {
                cur.children[i] = new TrieNode();
            }
            cur = cur.children[i];
        }
        cur.endOfWord = true;
    }

    public boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) {
                return false;
            }
            cur = cur.children[i];
        }
        return cur.endOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) {
                return false;
            }
            cur = cur.children[i];
        }
        return true;
    }
}

class TrieNode {
public:
    TrieNode* children[26];
    bool endOfWord;

    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        endOfWord = false;
    }
};

class PrefixTree {
    TrieNode* root;

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

    void insert(string word) {
        TrieNode* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (cur->children[i] == nullptr) {
                cur->children[i] = new TrieNode();
            }
            cur = cur->children[i];
        }
        cur->endOfWord = true;
    }

    bool search(string word) {
        TrieNode* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (cur->children[i] == nullptr) {
                return false;
            }
            cur = cur->children[i];
        }
        return cur->endOfWord;
    }

    bool startsWith(string prefix) {
        TrieNode* cur = root;
        for (char c : prefix) {
            int i = c - 'a';
            if (cur->children[i] == nullptr) {
                return false;
            }
            cur = cur->children[i];
        }
        return true;
    }
};

class TrieNode {
    constructor() {
        this.children = new Array(26).fill(null);
        this.endOfWord = false;
    }
}

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

    /**
     * @param {string} word
     * @return {void}
     */
    insert(word) {
        let cur = this.root;
        for (let c of word) {
            let i = c.charCodeAt(0) - 97;
            if (cur.children[i] === null) {
                cur.children[i] = new TrieNode();
            }
            cur = cur.children[i];
        }
        cur.endOfWord = true;
    }

    /**
     * @param {string} word
     * @return {boolean}
     */
    search(word) {
        let cur = this.root;
        for (let c of word) {
            let i = c.charCodeAt(0) - 97;
            if (cur.children[i] === null) {
                return false;
            }
            cur = cur.children[i];
        }
        return cur.endOfWord;
    }

    /**
     * @param {string} prefix
     * @return {boolean}
     */
    startsWith(prefix) {
        let cur = this.root;
        for (let c of prefix) {
            let i = c.charCodeAt(0) - 97;
            if (cur.children[i] === null) {
                return false;
            }
            cur = cur.children[i];
        }
        return true;
    }
}

public class TrieNode {
    public TrieNode[] children = new TrieNode[26];
    public bool endOfWord = false;
}

public class PrefixTree {
    private TrieNode root;

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

    public void Insert(string word) {
        TrieNode cur = root;
        foreach (char c in word) {
            int i = c - 'a';
            if (cur.children[i] == null) {
                cur.children[i] = new TrieNode();
            }
            cur = cur.children[i];
        }
        cur.endOfWord = true;
    }

    public bool Search(string word) {
        TrieNode cur = root;
        foreach (char c in word) {
            int i = c - 'a';
            if (cur.children[i] == null) {
                return false;
            }
            cur = cur.children[i];
        }
        return cur.endOfWord;
    }

    public bool StartsWith(string prefix) {
        TrieNode cur = root;
        foreach (char c in prefix) {
            int i = c - 'a';
            if (cur.children[i] == null) {
                return false;
            }
            cur = cur.children[i];
        }
        return true;
    }
}

type TrieNode struct {
	children [26]*TrieNode
	endOfWord bool
}

type PrefixTree struct {
	root *TrieNode
}

func Constructor() PrefixTree {
	return PrefixTree{root: &TrieNode{}}
}

func (this *PrefixTree) Insert(word string) {
	cur := this.root
	for _, c := range word {
		i := c - 'a'
		if cur.children[i] == nil {
			cur.children[i] = &TrieNode{}
		}
		cur = cur.children[i]
	}
	cur.endOfWord = true
}

func (this *PrefixTree) Search(word string) bool {
	cur := this.root
	for _, c := range word {
		i := c - 'a'
		if cur.children[i] == nil {
			return false
		}
		cur = cur.children[i]
	}
	return cur.endOfWord
}

func (this *PrefixTree) StartsWith(prefix string) bool {
	cur := this.root
	for _, c := range prefix {
		i := c - 'a'
		if cur.children[i] == nil {
			return false
		}
		cur = cur.children[i]
	}
	return true
}

class TrieNode {
    val children = arrayOfNulls<TrieNode>(26)
    var endOfWord = false
}

class PrefixTree {
    private val root = TrieNode()

    fun insert(word: String) {
        var cur = root
        for (c in word) {
            val i = c - 'a'
            if (cur.children[i] == null) {
                cur.children[i] = TrieNode()
            }
            cur = cur.children[i]!!
        }
        cur.endOfWord = true
    }

    fun search(word: String): Boolean {
        var cur = root
        for (c in word) {
            val i = c - 'a'
            if (cur.children[i] == null) {
                return false
            }
            cur = cur.children[i]!!
        }
        return cur.endOfWord
    }

    fun startsWith(prefix: String): Boolean {
        var cur = root
        for (c in prefix) {
            val i = c - 'a'
            if (cur.children[i] == null) {
                return false
            }
            cur = cur.children[i]!!
        }
        return true
    }
}

class TrieNode {
    var children: [TrieNode?]
    var endOfWord: Bool

    init() {
        self.children = Array(repeating: nil, count: 26)
        self.endOfWord = false
    }
}

class PrefixTree {
    private let root: TrieNode

    init() {
        self.root = TrieNode()
    }

    func insert(_ word: String) {
        var cur = root
        for c in word {
            let i = Int(c.asciiValue! - Character("a").asciiValue!)
            if cur.children[i] == nil {
                cur.children[i] = TrieNode()
            }
            cur = cur.children[i]!
        }
        cur.endOfWord = true
    }

    func search(_ word: String) -> Bool {
        var cur = root
        for c in word {
            let i = Int(c.asciiValue! - Character("a").asciiValue!)
            if cur.children[i] == nil {
                return false
            }
            cur = cur.children[i]!
        }
        return cur.endOfWord
    }

    func startsWith(_ prefix: String) -> Bool {
        var cur = root
        for c in prefix {
            let i = Int(c.asciiValue! - Character("a").asciiValue!)
            if cur.children[i] == nil {
                return false
            }
            cur = cur.children[i]!
        }
        return true
    }
}

Time & Space Complexity

Time complexity: $O(n)$ for each function call.
Space complexity: $O(t)$

Where $n$ is the length of the string and $t$ is the total number of TrieNodes created in the Trie.

2. Prefix Tree (Hash Map)

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

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

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

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

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

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

public class PrefixTree {
    private TrieNode root;

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

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

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

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

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool endOfWord = false;
};

class PrefixTree {
    TrieNode* root;

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

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

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

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

class TrieNode {
    constructor() {
        this.children = new Map();
        this.endOfWord = false;
    }
}

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

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

    /**
     * @param {string} word
     * @return {boolean}
     */
    search(word) {
        let cur = this.root;
        for (let c of word) {
            if (!cur.children.has(c)) {
                return false;
            }
            cur = cur.children.get(c);
        }
        return cur.endOfWord;
    }

    /**
     * @param {string} prefix
     * @return {boolean}
     */
    startsWith(prefix) {
        let cur = this.root;
        for (let c of prefix) {
            if (!cur.children.has(c)) {
                return false;
            }
            cur = cur.children.get(c);
        }
        return true;
    }
}

public class TrieNode {
    public Dictionary<char, TrieNode> children =
                            new Dictionary<char, TrieNode>();
    public bool endOfWord = false;
}

public class PrefixTree {
    private TrieNode root;

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

    public void Insert(string word) {
        TrieNode cur = root;
        foreach (char c in word) {
            if (!cur.children.ContainsKey(c)) {
                cur.children[c] = new TrieNode();
            }
            cur = cur.children[c];
        }
        cur.endOfWord = true;
    }

    public bool Search(string word) {
        TrieNode cur = root;
        foreach (char c in word) {
            if (!cur.children.ContainsKey(c)) {
                return false;
            }
            cur = cur.children[c];
        }
        return cur.endOfWord;
    }

    public bool StartsWith(string prefix) {
        TrieNode cur = root;
        foreach (char c in prefix) {
            if (!cur.children.ContainsKey(c)) {
                return false;
            }
            cur = cur.children[c];
        }
        return true;
    }
}

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

type PrefixTree struct {
	root *TrieNode
}

func Constructor() PrefixTree {
	return PrefixTree{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}

func (this *PrefixTree) Insert(word string) {
	cur := this.root
	for _, c := range word {
		if cur.children[c] == nil {
			cur.children[c] = &TrieNode{children: make(map[rune]*TrieNode)}
		}
		cur = cur.children[c]
	}
	cur.endOfWord = true
}

func (this *PrefixTree) Search(word string) bool {
	cur := this.root
	for _, c := range word {
		if cur.children[c] == nil {
			return false
		}
		cur = cur.children[c]
	}
	return cur.endOfWord
}

func (this *PrefixTree) StartsWith(prefix string) bool {
	cur := this.root
	for _, c := range prefix {
		if cur.children[c] == nil {
			return false
		}
		cur = cur.children[c]
	}
	return true
}

class TrieNode {
    val children = mutableMapOf<Char, TrieNode>()
    var endOfWord = false
}

class PrefixTree {
    private val root = TrieNode()

    fun insert(word: String) {
        var cur = root
        for (c in word) {
            cur.children.putIfAbsent(c, TrieNode())
            cur = cur.children[c]!!
        }
        cur.endOfWord = true
    }

    fun search(word: String): Boolean {
        var cur = root
        for (c in word) {
            if (c !in cur.children) {
                return false
            }
            cur = cur.children[c]!!
        }
        return cur.endOfWord
    }

    fun startsWith(prefix: String): Boolean {
        var cur = root
        for (c in prefix) {
            if (c !in cur.children) {
                return false
            }
            cur = cur.children[c]!!
        }
        return true
    }
}

class TrieNode {
    var children: [Character: TrieNode]
    var endOfWord: Bool

    init() {
        self.children = [:]
        self.endOfWord = false
    }
}

class PrefixTree {
    private let root: TrieNode

    init() {
        self.root = TrieNode()
    }

    func insert(_ word: String) {
        var cur = root
        for c in word {
            if cur.children[c] == nil {
                cur.children[c] = TrieNode()
            }
            cur = cur.children[c]!
        }
        cur.endOfWord = true
    }

    func search(_ word: String) -> Bool {
        var cur = root
        for c in word {
            if cur.children[c] == nil {
                return false
            }
            cur = cur.children[c]!
        }
        return cur.endOfWord
    }

    func startsWith(_ prefix: String) -> Bool {
        var cur = root
        for c in prefix {
            if cur.children[c] == nil {
                return false
            }
            cur = cur.children[c]!
        }
        return true
    }
}

Time & Space Complexity

Time complexity: $O(n)$ for each function call.
Space complexity: $O(t)$

Where $n$ is the length of the string and $t$ is the total number of TrieNodes created in the Trie.

Common Pitfalls

Confusing search and startsWith

A frequent mistake is returning true in search() whenever the traversal completes successfully, without checking the endOfWord flag. The search() method must verify that the final node marks the end of a complete word, while startsWith() only checks if the prefix path exists. For example, if "apple" is inserted, search("app") should return false (no word ends there), but startsWith("app") should return true.

Incorrect Character Index Calculation

When using an array-based Trie with 26 children, the character must be converted to an index using c - 'a'. A common error is using the ASCII value directly without subtraction, which causes index out of bounds errors. Another mistake is assuming uppercase letters, which would require c - 'A' instead. Always ensure the input constraints match the indexing scheme.

Forgetting to Initialize Child Nodes

When traversing during insert(), forgetting to create a new TrieNode when the child does not exist leads to null pointer exceptions on subsequent character accesses. The check if cur.children[i] == None: cur.children[i] = TrieNode() must happen before moving to the next node. Similarly, in the hash map approach, forgetting to add the character key before accessing it causes key errors.