ReviseAlgo Logo

Trie (Prefix Tree)

Trie Operations

Master Trie Operations: insertion, prefix search, exact word search, and recursive word deletion.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What are Trie Operations?

Trie Operations are the primary actions used to interact with prefix trees:
  • insert: Appending a word.
  • search: Validating if a word exists exactly.
  • startsWith: Validating if any stored word starts with a specific prefix.
  • delete: Removing a word from the Trie.

    • Why study them?

    Implementing a Trie from scratch (LeetCode 208) is one of the most frequent coding interview tasks. It tests your mastery of pointer navigation, node instantiations, and recursive memory cleanups.

    Where is it Used?

  • Vocabulary Engines: Dynamically inserting and looking up language dictionary words.
  • Auto-Correction Systems: Verifying typed tokens against valid prefixes.

    • 2. Mental Model: Drawing Paths in the Labyrinth

    Imagine walking through a maze of pathways:

  • Insert "dog": You check if path d exists. If not, you carve it. Then you look for o from d, and g from o. At g, you place a flag: "Word Ends Here".
  • Search "do": You follow the paths d and o. You reach the room o, but there is no green flag here. You return false because "do" is only a prefix, not a full word.
  • StartsWith "do": You follow d and o. The path exists, so you return true immediately—no flag check is required.

    • 3. Core Operations & Implementations

    Insertion & Deletion

  • Insertion: Step through characters. If a child index children[c - 'a'] is null, instantiate a new node. Advance curr = curr.children[c - 'a']. Mark curr.isEndOfWord = true at the end.
  • Deletion (Recursive): Clean nodes upwards. If a node is no longer needed (has no children and is not the end of another word), remove it from its parent's children array to save memory.

    • 4. Visual Trace: Word Deletion Path Cleanups

    Deleting "car" from a Trie that also stores "cat":

    5. Real-World Examples

  • Auto-Correction Engine: Deleting spelling tokens when removing words from custom user dictionary files.
  • Search Engine Query Autosuggest: Inserting search queries in bulk to index search path frequencies.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test boundary checks:
  • "Given a dictionary of words, design an autocomplete feature." -> Store words in a Trie. Traverse to the prefix node, then run DFS to collect valid keys.
  • "Implement Trie wildcard search." -> If character is ., loop and search recursively through all non-null children.

    • Common Mistakes

    Warning: 1. Memory Leaks in C++ Deletions: Deleting nodes without calling delete on the child pointer leads to memory fragmentation leaks.
    > 2. Wrong Deletion Halts: Deleting nodes that are shared by other words (e.g. deleting c and a when removing "car" in a Trie that also contains "cat"). Only delete a node if all its child pointers are null and isEndOfWord = false.

    7. Summary

  • Complexity: Insert/Search takes O(L) where L is word length.
  • StartsWith: Return true if the prefix path exists, ignoring the isEndOfWord flag.
  • Deletion: Clean unused leaf nodes recursively bottom-up to prevent memory leaks.

    • 8. Quiz

    Question 1: What is the time complexity of the delete operation for a word of length L? Answer: O(L) time, since we traverse down L levels, unmark the flag, and backtrack L steps.
    Question 2: In deleting a word, when is a node safe to be deleted from memory? Answer: A node is safe to delete if and only if it has no children (isEmpty(node) == true) and it does not mark the end of another word (isEndOfWord == false).
    Question 3: How does startsWith() differ from search()? Answer: search() checks if a word exists exactly, which requires isEndOfWord to be true at the final node. startsWith() only checks if a prefix path exists, returning true even if isEndOfWord is false.
    Question 4: True or False: You can implement a Trie using a HashMap for children instead of a size-26 array. Answer: True. A HashMap uses less memory for sparse nodes and supports any character set, but has slightly slower lookup times.
    Question 5: What is the output of search('apples') if we inserted 'apple' into the Trie? Answer: false. The path for "apples" will fail at character 's' because child pointer children['s' - 'a'] is null.