Difficulty: Intermediate | Prerequisites: Pointers in C, dynamic memory allocation (malloc/free), structs, recursion basics.
A trie (pronounced "try") is a tree-based data structure used to store and retrieve strings efficiently. It sits in the family of search trees, but unlike a binary search tree where each node holds a full key, a trie distributes the key across a path from root to leaf, one character per level. This makes it especially good at prefix-based lookups, which is why it comes up in autocomplete systems, spell checkers, and IP routing tables. You should already be comfortable with structs, pointers, and malloc in C before diving in.
A trie stores strings character by character along branching paths from a shared root. Each node has up to 26 children (for uppercase English letters), and you walk the tree one character at a time. Prefix queries are fast because every string sharing a prefix shares the same path down the tree.
Trie (prefix tree)
A k-ary search tree where each edge corresponds to a single character and each path from the root spells out a stored string (or prefix of one). In simple terms, think of it as a tree-shaped dictionary where words that start the same way share the same branches.
Node
A single element in the trie. Each node holds an array of child pointers (one per possible character) and, optionally, data about the strings passing through it. Think of each node as a single letter's "checkpoint" along the path of a word.
Root
The top-level node in the trie. It represents the empty string and is the starting point for every insertion, search, or deletion.
Edge
A link from a parent node to a child, labelled with a character. Following edges from the root spells out the stored string.
Prefix
The beginning portion of a string. In a trie, all strings sharing a prefix share the same initial path from the root. In simple terms, "WIL" is a prefix of "WILL", "WILLIAM", and "WILLY".
subtreeSum
A value stored at each node representing the total of some quantity (in this course, mangos) accumulated by all strings that pass through that node. This lets you answer prefix queries in O(L) time, where L is the length of the prefix, instead of traversing the entire subtree.
nodeTotal
The value stored at the node marking the end of a specific complete string. Distinct from subtreeSum: nodeTotal tracks one orangutan's mangos, subtreeSum tracks everyone whose name passes through that node.
The root node is empty and serves as the universal starting point.
Each node contains an array of 26 pointers (for A through Z), initially all NULL.
Inserting the string "BOB" creates (or follows) nodes along the path root -> B -> O -> B.
Multiple strings sharing a prefix share the same nodes up to the point where they diverge. "BOB" and "BETTY" both go through the root's B-child, then split at the second level.
To index into a node's children array, subtract 'A' from the character:
int index = character - 'A'; // 'A' -> 0, 'B' -> 1, ... 'Z' -> 25
This is explicitly part of the grading criteria. Every uppercase letter maps to an index in the range 0 to 25 inclusive.
Each new node should be dynamically allocated with all children set to NULL, subtreeSum set to 0, and nodeTotal set to 0:
struct TrieNode {
TrieNode *children[26];
int subtreeSum;
int nodeTotal;
};
A helper function to allocate and initialise a node keeps the code clean and avoids repeating the same malloc/memset logic.
When you feed an orangutan (event type 1), walk the trie character by character along the orangutan's name. At each node along the path, increment subtreeSum by the feeding amount. At the final node (the one representing the last character of the name), also increment nodeTotal.
If a node does not exist at any step along the path, create it. This means you only insert names you actually encounter, not all possible names up front.
For event type 3 (query), walk the trie along the prefix characters. If you reach the end of the prefix without hitting a NULL pointer, the subtreeSum at that node is your answer. If you hit NULL before finishing the prefix, the answer is 0, because no stored name has that prefix.
This is O(L) where L is the prefix length, at most 20 characters. Without subtreeSum you would need to recurse through the entire subtree to sum values, which could be much slower.
When an orangutan changes its name (event type 2), you need to move its accumulated mangos from the old name path to the new name path. The recommended approach:
Walk the old name path and subtract the orangutan's nodeTotal from every ancestor's subtreeSum. Set the old endpoint's nodeTotal to 0.
Walk the new name path and add the same value to every ancestor's subtreeSum. Set the new endpoint's nodeTotal to that value.
This is equivalent to "adding negative its original value to the old name and positive its original value to the new name," as the assignment hints suggest.
Time complexity per operation:
Feeding (event 1): O(L), where L is the name length (at most 20).
Name change (event 2): O(L_old + L_new), two walks of at most 20 characters each.
Prefix query (event 3): O(L), where L is the prefix length.
Space complexity: O(total characters across all names x 26) in the worst case, since each node has 26 child pointers. In practice, shared prefixes reduce this considerably.
Tries power the autocomplete in your phone keyboard and search engines, where fast prefix lookup across millions of strings is essential. They also appear in network routers for IP address lookup (longest prefix matching) and in bioinformatics for indexing DNA sequences.
Students often think a trie node stores the character it represents. It does not. The character is implied by which index in the parent's children array points to it.
Students sometimes update only the endpoint node's subtreeSum on a feeding, forgetting to update every ancestor along the path. Every node from the root to the endpoint must be incremented.
Students confuse nodeTotal and subtreeSum. nodeTotal is for one specific complete name. subtreeSum is the aggregate of nodeTotal for that node plus all descendants.
Students forget to handle the name change as two operations (subtract from old path, add to new path) and instead try to "move" the node, which breaks the trie structure.
⚠️ The assignment mandates a trie. Solutions without one are capped at 50 points. Make sure you can implement one from scratch.
⚠️ The subtreeSum optimisation is what makes prefix queries efficient. Without it, you would need a full subtree traversal for every query, and that will likely time out on large inputs.
⚠️ Name changes are the most common source of bugs. Trace through the sample cases by hand to verify your subtraction/addition logic.
⚠️ Programs must compile with gcc -std=gnu11 -lm and produce no extra output (no prompts, no debug prints).
T/F: A trie node for the letter 'C' stores the character 'C' inside the node. False. The character is implied by the parent's pointer index.
T/F: When feeding an orangutan, you only update the node at the end of the name. False. You update subtreeSum at every node along the path from root to endpoint.
Fill in the blank: To convert an uppercase letter to a trie index, you compute character - ____. 'A'
T/F: If you query prefix "XYZ" and no name starts with "X", you return 0. True. You hit a NULL child at the very first character and return 0.
T/F: During a name change, you should delete the old nodes from the trie. False. You subtract the value from the old path but leave the nodes in place. Other names might share those prefix nodes.
Q: What is the time complexity of a prefix query in a trie that stores subtreeSum at each node, given a prefix of length L?
A: O(L). You walk L nodes and read the subtreeSum at the last one.
Q: An orangutan named "WILL" has eaten 6 mangos. It changes its name to "MATT". Describe what happens in the trie.
A: Walk the path W -> I -> L -> L and subtract 6 from subtreeSum at each node. Set nodeTotal at the final L to 0. Then walk (or create) the path M -> A -> T -> T, adding 6 to subtreeSum at each node and setting nodeTotal at the final T to 6.
Q: Why do we store subtreeSum rather than computing it on the fly for each query?
A: Computing the sum on the fly would require visiting every node in the subtree, which in the worst case touches all stored names. Storing subtreeSum gives O(L) query time at the cost of O(L) extra work during each update.
Q: If "BOB" has eaten 5 mangos and "BETTY" has eaten 3, what is the subtreeSum at the root's B-child?
A: 8. Both names pass through the B-child, so it accumulates both totals.
Q: What happens if you query a prefix that is longer than any stored name?
A: You will hit a NULL pointer before reaching the end of the prefix and return 0.
This connects to binary search trees, which you covered earlier, since a trie is another flavour of search tree with different trade-offs (fast prefix queries, higher memory use). It also ties into hash maps: a hash map can look up an exact name in O(1) average time, but cannot efficiently answer "sum all names starting with X" without scanning every entry. If you go on to study algorithms, tries appear again in string matching (Aho-Corasick) and compression (Huffman coding uses a related tree structure).
trie, prefix tree, digital tree, retrieval tree, radix tree, trie in C, trie node struct, subtree sum, prefix query, trie insert, trie search, COP 3502, Computer Science I, UCF, string data structure, autocomplete data structure, name lookup trie