How to Solve: Implement Trie (Prefix Tree) – Complete Guide for FAANG Interviews

How to Solve: Implement Trie (Prefix Tree) – Complete Guide for FAANG Interviews

? Introduction

"This single data structure appears in 1 out of every 3 onsite interviews—master it, and you’ll instantly stand out as a candidate who understands efficient string search, autocomplete, and dictionary lookups at scale."

? WHAT YOU NEED TO KNOW FIRST

Before diving into Tries, ensure you understand: 1. Tree Data Structures (Nodes, children, traversal) 2. Hash Maps / Dictionaries (Key-value lookups, O(1) average case) 3. Recursion vs. Iteration (DFS traversal, backtracking)

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these steps every time you implement a Trie:

1. Define the TrieNode class
2. children: A dictionary (or array) to store child nodes.

3. is_end: A boolean flag marking the end of a word.

4. Initialize the Trie

5. Create a root node (TrieNode()).

6. Implement insert(word)

7. Start at the root.
8. For each character in word:
   • If the character doesn’t exist in children, create a new TrieNode.
   • Move to the child node.

9. Mark the last node as is_end = True.

10. Implement search(word) (Exact Match)

11. Start at the root.
12. For each character in word:
    • If the character doesn’t exist, return False.
    • Move to the child node.

13. Return True only if is_end is True.

14. Implement startsWith(prefix)

15. Same as search, but return True if the path exists (don’t check is_end).

16. Handle Edge Cases

17. Empty string ("").
18. Duplicate words.

19. Case sensitivity (convert to lowercase if needed).

20. Optimize for Follow-ups

21. Deletion: Recursively remove nodes if no children left.
22. Memory: Use a Radix Tree if space is a concern.

? WORKED EXAMPLES

Example 1 – Basic: Implement Trie (Prefix Tree)

Problem: Design a Trie with insert, search, and startsWith methods.

Thought Process

1. TrieNode Structure: Each node has children (dict) and is_end (bool).
2. Insert: Traverse char-by-char, create nodes if missing.
3. Search: Traverse, check is_end at the end.
4. startsWith: Traverse, return True if path exists.

Python Code

class TrieNode:

    def __init__(self):

        self.children = {}  # char -> TrieNode

        self.is_end = 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 = 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


    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

Time & Space Complexity

Why this works: - Insertion builds the Trie incrementally, ensuring all prefixes are stored. - Search leverages the Trie’s structure to check for exact matches in O(L) time. - startsWith reuses the same traversal but ignores is_end.

Example 2 – Medium: Word Search II (LeetCode 212)

Problem: Given an m x n board and a list of words, return all words on the board (each word must be formed by adjacent letters, no reuse).

Thought Process

1. Trie for Prefix Matching: Insert all words into a Trie.
2. DFS + Backtracking: Traverse the board, checking if the current path exists in the Trie.
3. Early Termination: If a word is found, remove it from the Trie to avoid duplicates.

Python Code

class TrieNode:

    def __init__(self):

        self.children = {}

        self.word = None  # Store the word at the end node

class Solution:

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:

        # Build Trie

        root = TrieNode()

        for word in words:

            node = root

            for char in word:

                if char not in node.children:

                    node.children[char] = TrieNode()

                node = node.children[char]

            node.word = word  # Mark end of word


        # DFS on board

        res = []

        m, n = len(board), len(board[0])


        def dfs(i, j, node):

            char = board[i][j]

            if char not in node.children:

                return


            next_node = node.children[char]

            if next_node.word:

                res.append(next_node.word)

                next_node.word = None  # Avoid duplicates


            # Mark as visited

            board[i][j] = "#"

            for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:

                ni, nj = i + di, j + dj

                if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != "#":

                    dfs(ni, nj, next_node)

            board[i][j] = char  # Backtrack


        for i in range(m):

            for j in range(n):

                dfs(i, j, root)

        return res

Time & Space Complexity

Why this works: - Trie efficiently checks prefixes, reducing redundant searches. - DFS + Backtracking explores all possible paths while avoiding revisits. - Early Termination (next_node.word = None) prevents duplicate results.

Example 3 – Hard/Follow-up: Design Add and Search Words Data Structure (LeetCode 211)

Problem: Design a data structure that supports: - addWord(word) - search(word) (where . matches any character)

Thought Process

1. Trie for Exact Matching: Standard Trie for addWord.
2. Wildcard Handling: Use DFS when encountering . to explore all possible paths.

Python Code

class TrieNode:

    def __init__(self):

        self.children = {}

        self.is_end = False

class WordDictionary:

    def __init__(self):

        self.root = TrieNode()


    def addWord(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 = True


    def search(self, word: str) -> bool:

        def dfs(node, i):

            if i == len(word):

                return node.is_end

            char = word[i]

            if char == ".":

                for child in node.children.values():

                    if dfs(child, i + 1):

                        return True

                return False

            else:

                if char not in node.children:

                    return False

                return dfs(node.children[char], i + 1)


        return dfs(self.root, 0)

Time & Space Complexity

Why this works: - Trie efficiently stores words for exact matches. - DFS for Wildcards explores all possible paths when . is encountered. - Early Termination returns as soon as a match is found.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. A Trie is just a tree of characters where each path represents a word. Here’s the playbook:

1. Start with TrieNode: A node has children (dict) and is_end (bool).
2. Insert: Traverse char-by-char, create nodes if missing, mark the end.
3. Search: Traverse, check is_end at the end.
4. Prefix Search: Same as search, but ignore is_end.
5. Follow-ups:
6. Deletion? Recursively remove nodes if no children.
7. Wildcards? Use DFS to explore all paths.
8. Memory? Compress with a Radix Tree.

You’ve got this. Now go implement it—fast, clean, and without bugs. Good luck!

? Final Notes

• Practice Variations: Try autocomplete, longest common prefix, and word break.
• Whiteboard First: Sketch the Trie before coding.
• Edge Cases: Always test "", duplicates, and case sensitivity.

This guide is 100% interview-ready—use it to dominate your next Trie problem! ?