Source: Comprehensive Guide to Tries, Heaps, and Priority Queues – UCF Computer Science I
Difficulty: Intermediate | Prerequisites: Basic tree structures, pointers/references, recursion.
Tags: trie, prefix tree, dictionary lookup, autocomplete, string search, isEndOfWord, trie insert, trie delete, trie search, spell check, IP routing
Tries sit in the part of the course where you move beyond general-purpose trees (BSTs, AVL trees) into specialised structures built for particular data types. A trie is purpose-built for strings: it exploits the fact that many strings share common beginnings (prefixes) so you can store and search them far more efficiently than with, say, a hash map of whole words. If you are comfortable with tree traversal and understand how pointers link parent nodes to children, you have what you need. Tries come up in interviews, in systems work (routers use them), and anywhere fast prefix matching matters.
A trie is a tree where each node represents a single character, and paths from root to marked endpoints spell out stored strings. Insert, search, and delete all run in O(n) time, where n is the length of the string, because you simply walk one node per character with no backtracking.
Trie (prefix tree)
A specialised tree structure for storing and retrieving strings. Each edge or child slot corresponds to a character, and shared prefixes share the same path from the root. Think of it as a branching dictionary where you spell words one letter at a time as you walk down the tree.
isEndOfWord flag
A boolean on each node that marks whether the path from the root to this node forms a complete, stored string. In simple terms, this is how the trie knows "cat" is a real word and not just the first three letters of "category."
Prefix matching
The ability to find all strings that begin with a given sequence of characters. Because every string sharing a prefix shares the same path in the trie, you only need to walk to the end of the prefix and then explore all descendants.
Node (trie node)
A structure containing an array of child pointers (one per possible character, typically 26 for lowercase English) and the isEndOfWord flag. Unused child slots are NULL.
An array of 26 pointers (for lowercase a–z), each pointing to a child node for the corresponding letter.
A boolean flag, isEndOfWord, indicating whether the path to this node is a complete stored string.
Unused pointer slots are set to NULL.
The root node is initialised with all pointers NULL and isEndOfWord set to false. It does not itself represent a character.
The standard implementation assumes lowercase English letters only (a–z), so each node needs exactly 26 slots.
To support uppercase, digits, or Unicode you would widen the array or switch to a hash map of children, but the exam typically uses the 26-slot version.
Start at the root.
For each character in the string:
Compute the index (e.g. c - 'a' for character c).
If the child pointer at that index is NULL, create a new node there.
Move to the child node.
After the last character, set isEndOfWord = true on the current node.
Example: inserting "cat" creates or follows nodes for 'c', then 'a', then 't', and marks the 't' node.
Start at the root.
For each character, follow the corresponding child pointer.
If any pointer along the way is NULL, the string is not in the trie – return false immediately.
After the last character, check isEndOfWord:
True: the string exists.
False: the characters are present but only as a prefix of some longer word, not as a stored string themselves.
Recursively traverse to the end of the target string.
Clear the isEndOfWord flag on the final node.
On the way back up, remove any node that is no longer part of another stored string (i.e. it has no children and is not itself an end-of-word marker).
If the string does not exist in the trie, terminate early and change nothing.
Operation | Time Complexity | Notes |
|---|---|---|
Insert | O(n) | n = length of the string |
Search | O(n) | One pointer lookup per character |
Delete | O(n) | Traverse then clean up on return |
Space complexity per node is O(alphabet size), so O(26) for lowercase English. Total space depends on how many strings you store and how much prefix overlap they have.
Autocomplete in search bars and phone keyboards: the trie stores the dictionary, and as you type each letter the system walks the trie to suggest completions.
IP routing tables in network routers use a variant (PATRICIA trie) to match the longest prefix of an IP address to a forwarding rule, which is how your data packets find their way across the internet.
Students often assume a search returning true at the last character means the word exists. It does not, unless isEndOfWord is also true. "car" might trace a valid path in a trie that only contains "card," but isEndOfWord at 'r' would be false.
Students sometimes think deletion means simply unsetting isEndOfWord. You also need to remove orphan nodes that no longer contribute to any stored string, or you leak memory.
The root node does not represent any character. It is an empty starting point. Forgetting this leads to off-by-one errors in indexing.
Tries do not inherently sort their contents, but a depth-first traversal does produce strings in lexicographic order, because child pointers are indexed alphabetically.
⚠️ You will almost certainly be asked to trace an insertion or search through a trie, step by step. Practise drawing the tree after each insertion.
⚠️ The distinction between "the path exists" and "isEndOfWord is true" is a classic exam question. Know it cold.
⚠️ Be ready to state and justify the O(n) time complexity for all three operations, and to explain why n here is the string length, not the number of strings stored.
⚠️ Deletion is the trickiest operation. Expect a question that asks you to delete a word that shares a prefix with another word (e.g. delete "car" from a trie containing "car" and "card").
True or false: In a standard trie for lowercase English, each node contains an array of 52 pointers.
Fill in the blank: The time complexity of searching for a string of length n in a trie is ______.
True or false: If "app" is in the trie, the node for the second 'p' will have isEndOfWord set to true.
Fill in the blank: When deleting a word, you should remove nodes on the way back up only if they have no ______ and their isEndOfWord is ______.
True or false: The root node of a trie stores the first character of every inserted string.
Answers: 1. False (26 pointers). 2. O(n). 3. True. 4. children; false. 5. False (the root is empty; children of the root store first characters).
Q: You insert "cat", "car", and "card" into an empty trie, then delete "car". Describe the state of the trie after the deletion.
A: The path c → a → r → d still exists because "card" is still stored. The node for 'r' has its isEndOfWord flag cleared (since "car" was removed), but the node itself remains because it is on the path to 'd'. The node for 't' (from "cat") is unaffected.
Q: Why is trie search O(n) rather than O(n log n) or O(log n)?
A: Each character requires exactly one array index lookup (constant time), and you do this once per character. There is no comparison-based branching or backtracking, so the total work is proportional to the string length n.
Q: A trie stores "he", "heat", "heap", and "hero". How many nodes (excluding the root) does the trie contain?
A: 8 nodes. The shared prefix "he" accounts for 2 nodes. From 'e': 'a' branches to 't' and 'p' (3 more nodes), and 'r' branches to 'o' (2 more nodes). Adding the 'e' node shared by all: h(1), e(2), a(3), t(4), p(5), r(6), o(7) – that is 7 nodes plus checking: h, e, then children of e are a and r. a's children are t and p. r's child is o. Total: h, e, a, t, p, r, o = 7 nodes.
Q: What happens if you search for "he" in the trie above?
A: The search follows h → e and checks isEndOfWord on the 'e' node. Because "he" was inserted, the flag is true and the search returns true. If "he" had not been inserted (only "heat", "heap", "hero"), the flag would be false and the search would return false, even though the path exists.
This connects to binary search trees because both are tree-based search structures, but BSTs compare whole keys at each node while tries decompose keys character by character. Understanding that trade-off helps you pick the right structure for the problem.
Tries also connect to hash tables: both offer fast lookups, but hash tables cannot do prefix queries efficiently. If the exam asks you to compare data structures for a dictionary with autocomplete, the trie wins on prefix operations while the hash table wins on single exact-match lookups.
trie, prefix tree, digital tree, radix tree, PATRICIA trie, autocomplete data structure, dictionary lookup tree, string search tree, isEndOfWord, trie insert algorithm, trie delete algorithm, trie search algorithm, trie time complexity, trie vs hash table, trie vs BST, spell checker data structure, IP routing trie, CS 101 UCF tries