Trie Node Representation - Learning Module

Loading content...

0/276

Node Structure — Children Map/Array and End-of-Word Flag

The Anatomy of a Trie Node

Every powerful data structure has a fundamental building block—a node—whose design determines the structure's capabilities, performance characteristics, and practical limitations. For tries, this building block is deceptively simple at first glance, yet its design involves nuanced trade-offs that separate naive implementations from production-ready systems.

In this page, we will dissect the trie node completely. We will understand not just what fields a trie node contains, but why those fields exist, how they enable the operations tries are famous for, and what alternative designs are available. By the end, you will be able to design trie nodes tailored to specific problem constraints—a skill that distinguishes engineers who truly understand data structures from those who merely memorize interfaces.

What You Will Learn

By completing this page, you will understand: (1) The two essential components of every trie node—children references and the end-of-word marker, (2) Why these components are necessary and sufficient for all trie operations, (3) How the node design maps directly to the trie's conceptual model of shared prefixes, and (4) The foundational reasoning that will inform deeper exploration of implementation trade-offs in subsequent pages.

The Conceptual Foundation: What Must a Trie Node Do?

Before examining specific implementations, let's establish what functionality a trie node must provide. This requirements-first approach ensures we understand why certain design choices are made, rather than accepting them as arbitrary conventions.

The Trie's Core Promise:

A trie stores a collection of strings such that:

Strings sharing a common prefix share the same path from the root
Each character in a string corresponds to exactly one edge/transition
We can determine whether a string exists in the collection
We can find all strings starting with a given prefix

From these requirements, we can derive what each node must provide:

Derived Node Requirements

•Character Transition Storage — From any node, we must be able to follow a specific character to reach the appropriate child node. This means each node must somehow store or reference its children, keyed by character.
•Word Boundary Marking — Since prefixes of stored words are also valid paths in the trie, we need a way to distinguish 'this path represents a complete word' from 'this path is merely a prefix of some word'. Without this, we couldn't tell if 'car' exists when 'cart' is stored.
•Traversal Capability — During prefix searches, we must be able to enumerate all children of a node to explore all possible continuations. This influences how we store children.

Minimalism in Design

Notice that we do NOT need to store the character that leads to a node within the node itself. That character is implicit in how we reached the node—it's the key used to look up this node from its parent. This is a subtle but important insight: the edge label (the character) belongs to the parent-child relationship, not to the child node alone.

The Children Reference: Mapping Characters to Child Nodes

The first and most critical component of a trie node is its children reference—the mechanism by which we navigate from one character to the next. This is where the trie's character-by-character navigation becomes concrete.

The Fundamental Question:

Given a node and a character, how do we efficiently determine:

Does a child for this character exist?
If so, what is that child node?

This is essentially a mapping problem: we need to map characters (keys) to child nodes (values). How we implement this mapping profoundly affects the trie's performance characteristics.

Children Storage Strategies Overview
Strategy	Implementation	Lookup Time	Space Usage	Best For
Fixed-Size Array	Array indexed by character code	O(1)	O(alphabet size) per node	Small, fixed alphabets (e.g., lowercase letters)
Hash Map	Hash table mapping char → node	O(1) average	O(actual children)	Large or variable alphabets (e.g., Unicode)
Sorted Array	Array of (char, node) pairs, sorted	O(log k)	O(actual children)	Memory-critical with moderate lookup needs
Linked List	List of (char, node) pairs	O(k)	O(actual children)	Very sparse nodes (rarely used in practice)

The Array Approach in Detail:

The most straightforward approach uses a fixed-size array where the index corresponds to the character's position in the alphabet. For example, with lowercase English letters:

Index 0 → 'a'
Index 1 → 'b'
...
Index 25 → 'z'

To find the child for character 'c', we simply access children[2]. If the entry is null (or equivalent), no child exists. Otherwise, we have our child node.

Advantages of the Array Approach:

Constant-time access: O(1) lookup regardless of how many children exist
Simplicity: No collision handling, no resizing
Cache efficiency: Contiguous memory allocation

Disadvantages of the Array Approach:

Memory overhead: Every node allocates space for ALL possible children
Wasted space: Most nodes have few actual children
Fixed alphabet: Cannot handle characters outside the predefined range

trie-node-array.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * TrieNode using fixed-size array for children storage
 * Optimized for lowercase English letters (a-z)
 */
class TrieNodeArray {
    // Fixed-size array: index i corresponds to character 'a' + i
    // null means no child exists for that character
    children: (TrieNodeArray | null)[];
    
    // Marks whether a word ends at this node
    isEndOfWord: boolean;
    
    constructor() {
        // Allocate space for all 26 lowercase letters
        this.children = new Array(26).fill(null);
        this.isEndOfWord = false;
    }
    
    /**
     * Get child for a specific character
     * @param char - The character to look up (must be 'a'-'z')
     * @returns The child node, or null if none exists
     * Time: O(1)
     */
    getChild(char: string): TrieNodeArray | null {
        const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
        return this.children[index];
    }
    
    /**
     * Set child for a specific character
     * @param char - The character key (must be 'a'-'z')
     * @param node - The child node to store
     * Time: O(1)
     */
    setChild(char: string, node: TrieNodeArray): void {
        const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
        this.children[index] = node;
    }
    
    /**
     * Check if a child exists for the given character
     * Time: O(1)
     */
    hasChild(char: string): boolean {
        return this.getChild(char) !== null;
    }
    
    /**
     * Get all existing children for iteration
     * Useful for prefix enumeration
     * Time: O(alphabet size) = O(26) = O(1)
     */
    getAllChildren(): { char: string; node: TrieNodeArray }[] {
        const result: { char: string; node: TrieNodeArray }[] = [];
        for (let i = 0; i < 26; i++) {
            if (this.children[i] !== null) {
                result.push({
                    char: String.fromCharCode('a'.charCodeAt(0) + i),
                    node: this.children[i]!
                });
            }
        }
        return result;
    }
}

The Hash Map Alternative: Dynamic Character Storage

The fixed-size array approach works beautifully for small, well-defined alphabets like lowercase English letters. But what if we need to handle:

Mixed-case strings (52 letters)
Alphanumeric content (62 characters)
Full ASCII (128 characters)
Unicode text (potentially 1,114,112 code points!)

Allocating an array of 1 million+ entries for every node is absurd. This is where hash maps (also called hash tables or dictionaries) become essential.

The Hash Map Approach:

Instead of pre-allocating space for every possible character, we store only the children that actually exist. A hash map provides near-constant time lookup while using space proportional to actual children.

trie-node-map.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * TrieNode using Map (hash map) for children storage
 * Supports any character set, including full Unicode
 */
class TrieNodeMap {
    // Map from character to child node
    // Only stores children that actually exist
    children: Map<string, TrieNodeMap>;
    
    // Marks whether a word ends at this node
    isEndOfWord: boolean;
    
    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
    }
    
    /**
     * Get child for a specific character
     * @param char - Any character (Unicode supported)
     * @returns The child node, or undefined if none exists
     * Time: O(1) average
     */
    getChild(char: string): TrieNodeMap | undefined {
        return this.children.get(char);
    }
    
    /**
     * Set child for a specific character
     * @param char - Any character (Unicode supported)
     * @param node - The child node to store
     * Time: O(1) average
     */
    setChild(char: string, node: TrieNodeMap): void {
        this.children.set(char, node);
    }
    
    /**
     * Check if a child exists for the given character
     * Time: O(1) average
     */
    hasChild(char: string): boolean {
        return this.children.has(char);
    }
    
    /**
     * Get number of actual children
     * Time: O(1)
     */
    getChildCount(): number {
        return this.children.size;
    }
    
    /**
     * Iterate over all children
     * Useful for prefix enumeration
     * Time: O(k) where k is number of children
     */
    *iterateChildren(): Generator<[string, TrieNodeMap]> {
        for (const entry of this.children) {
            yield entry;
        }
    }
    
    /**
     * Remove a child (needed for deletion)
     * Time: O(1) average
     */
    removeChild(char: string): boolean {
        return this.children.delete(char);
    }
}
 
// Example usage demonstrating Unicode support
const unicodeTrie = new TrieNodeMap();
const child1 = new TrieNodeMap();
const child2 = new TrieNodeMap();
const child3 = new TrieNodeMap();
 
// Works with any characters!
unicodeTrie.setChild('α', child1);  // Greek letter
unicodeTrie.setChild('中', child2);  // Chinese character
unicodeTrie.setChild('🚀', child3);  // Emoji
 
console.log(unicodeTrie.hasChild('α'));  // true
console.log(unicodeTrie.hasChild('a'));  // false
console.log(unicodeTrie.getChildCount()); // 3

Language Implementation Details

Different languages provide hash map implementations with varying performance characteristics. JavaScript's Map and Python's dict are highly optimized. Java's HashMap has good average-case performance but can degrade with poor hash functions. In performance-critical applications, understanding your language's hash map implementation matters.

The End-of-Word Flag: Distinguishing Words from Prefixes

The second essential component of a trie node is the end-of-word flag (sometimes called isWord, isTerminal, or isEndOfWord). This simple boolean field solves a fundamental problem that arises from the trie's prefix-sharing design.

The Problem:

Consider a trie containing the word "cart". The path from root is:

root → 'c' → 'a' → 'r' → 't'

Now suppose we want to check if "car" is in the trie. We can successfully traverse:

root → 'c' → 'a' → 'r'

We reached a valid node! But does "car" exist as a stored word, or is it merely a prefix of "cart"? Without additional information, we cannot tell.

The Solution:

Each node carries a boolean flag indicating whether a complete word ends at that node. When we insert "car", we traverse to the 'r' node and set isEndOfWord = true. When we later insert "cart", we continue from 'r' to 't' and set that node's flag to true as well.

Now both "car" and "cart" are marked as complete words, even though "car" is a prefix of "cart".

With End-of-Word Flag

•Can distinguish 'car' from prefix of 'cart'
•Enables correct word existence checks
•Supports word counting
•Required for proper deletion
•Minimal space overhead (1 bit per node)

Without End-of-Word Flag

•Cannot tell if path represents a word
•Only leaf nodes would be words
•Cannot store words that are prefixes
•Fundamentally broken for most use cases
•Would require word-ending sentinel characters

Visualizing the End-of-Word Flag:

Consider a trie storing: ["a", "an", "and", "ant", "anti"]

        (root)
           │
           a [✓]          ← 'a' is a complete word
           │
           n [✓]          ← 'an' is a complete word
          / \
         d   t
        [✓]  [✓]          ← 'and' and 'ant' are complete words
             │
             i [✓]        ← 'anti' is a complete word

Notice that:

Every node along the path can potentially be a word ending
The flag is set independently for each node
Internal nodes (like 'n') can have the flag set
The flag doesn't affect the node's children in any way

Alternative: Word-Ending Sentinel

Some implementations avoid the boolean flag by appending a special sentinel character (like '$' or '\0') to every word before insertion. The word 'car' becomes 'car$'. This makes the sentinel node a leaf and the check is simply: does this child exist? However, this approach adds a node per word and complicates the logic. The boolean flag is generally preferred.

How Node Design Enables Trie Operations

Now that we understand both components of a trie node, let's see how they work together to enable the fundamental trie operations. This connection between node design and operation implementation is crucial for understanding why tries work the way they do.

Insert Operation:

To insert a word like "cat":

Start at root
For 'c': Check if child exists; if not, create it. Move to child.
For 'a': Check if child exists; if not, create it. Move to child.
For 't': Check if child exists; if not, create it. Move to child.
Set isEndOfWord = true on the final node.

The children reference enables navigation; the flag marks completion.

trie-operations.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/**
 * Complete Trie implementation demonstrating
 * how node design enables operations
 */
class Trie {
    private root: TrieNode;
    
    constructor() {
        this.root = new TrieNode();
    }
    
    /**
     * Insert a word into the trie
     * Time: O(m) where m is word length
     * Space: O(m) for new nodes in worst case
     */
    insert(word: string): void {
        let current = this.root;
        
        for (const char of word) {
            // Use children reference to navigate or create path
            if (!current.children.has(char)) {
                current.children.set(char, new TrieNode());
            }
            current = current.children.get(char)!;
        }
        
        // Use end-of-word flag to mark this word as complete
        current.isEndOfWord = true;
    }
    
    /**
     * Search for exact word match
     * Returns true only if the word exists AND is marked as complete
     * Time: O(m)
     */
    search(word: string): boolean {
        const node = this.traverse(word);
        
        // Node must exist AND be marked as a complete word
        return node !== null && node.isEndOfWord;
    }
    
    /**
     * Check if any word starts with the given prefix
     * Time: O(m)
     */
    startsWith(prefix: string): boolean {
        // For prefix, we only need the path to exist
        // End-of-word flag doesn't matter for prefix matching
        return this.traverse(prefix) !== null;
    }
    
    /**
     * Helper: Traverse the trie following a string
     * Returns the final node, or null if path doesn't exist
     */
    private traverse(str: string): TrieNode | null {
        let current = this.root;
        
        for (const char of str) {
            // Use children reference to navigate
            if (!current.children.has(char)) {
                return null;  // Path doesn't exist
            }
            current = current.children.get(char)!;
        }
        
        return current;
    }
    
    /**
     * Find all words with a given prefix
     * Demonstrates iterating over children
     * Time: O(m + k) where k is total characters in matching words
     */
    findWordsWithPrefix(prefix: string): string[] {
        const results: string[] = [];
        const prefixNode = this.traverse(prefix);
        
        if (prefixNode === null) {
            return results;
        }
        
        // DFS to find all complete words under this node
        this.collectWords(prefixNode, prefix, results);
        return results;
    }
    
    /**
     * DFS helper to collect all words from a given node
     */
    private collectWords(
        node: TrieNode, 
        currentWord: string, 
        results: string[]
    ): void {
        // If this node marks a complete word, add it
        if (node.isEndOfWord) {
            results.push(currentWord);
        }
        
        // Recursively explore all children
        for (const [char, childNode] of node.children) {
            this.collectWords(childNode, currentWord + char, results);
        }
    }
}
 
class TrieNode {
    children: Map<string, TrieNode> = new Map();
    isEndOfWord: boolean = false;
}
 
// Demonstration
const trie = new Trie();
trie.insert("car");
trie.insert("card");
trie.insert("care");
trie.insert("cart");
trie.insert("cat");
 
console.log(trie.search("car"));   // true - exact match, marked as word
console.log(trie.search("ca"));    // false - path exists but not a word
console.log(trie.startsWith("ca")); // true - prefix exists
 
console.log(trie.findWordsWithPrefix("car"));
// ["car", "card", "care", "cart"]

Memory Layout: How Nodes Form the Trie

Understanding how trie nodes are organized in memory helps clarify both the strengths and costs of the data structure. Let's trace through building a small trie and examine what actually exists in memory.

Building a Trie for ["to", "tea", "ted", "ten", "inn"]:

Step by step:

Create root node (empty, no flag)
Insert "to": root→t→o, mark 'o' as end
Insert "tea": root→t→e→a, mark 'a' as end
Insert "ted": root→t→e→d, mark 'd' as end (reuses t→e path)
Insert "ten": root→t→e→n, mark 'n' as end (reuses t→e path)
Insert "inn": root→i→n→n, mark final 'n' as end

The resulting structure:

Memory Representation of Nodes
Node ID	Reached Via	Children	isEndOfWord	Words Passing Through
N0 (root)		{t: N1, i: N4}	false	all words
N1	t	{o: N2, e: N3}	false	to, tea, ted, ten
N2	o	{}	TRUE ✓	to
N3	e	{a: N6, d: N7, n: N8}	false	tea, ted, ten
N4	i	{n: N5}	false	inn
N5	n	{n: N9}	false	inn
N6	a	{}	TRUE ✓	tea
N7	d	{}	TRUE ✓	ted
N8	n	{}	TRUE ✓	ten
N9	n	{}	TRUE ✓	inn

Key Observations:

Shared prefixes = Shared nodes: Words "tea", "ted", and "ten" share nodes N1 and N3 (the "te" path). This is the source of trie space efficiency for words with common prefixes.
Internal nodes can be word endings: If we added "te" as a word, node N3 would have isEndOfWord = true. The structure wouldn't change—only the flag.
Leaf nodes are always word endings: Every leaf (nodes with no children) MUST be an end-of-word node. If it weren't, the path to it would have no purpose.
Node count = Total unique prefixes + 1: Including the empty prefix (root), our trie has 10 nodes representing all unique prefixes of our 5 words.
Character storage: Notice that we don't store the character 't' inside node N1. The character is implicit in the parent's children map. This subtle point means we're not storing each character twice.

Space Reality Check

While sharing prefixes saves space, each node has overhead: the children collection (even if empty) and the flag. For very short words or words with few shared prefixes, a trie might use MORE space than just storing the strings. We'll analyze this precisely in the space complexity page.

The Complete Node Template

Let's consolidate everything into production-ready node templates that you can adapt for various scenarios. These templates include common extensions that are often needed in practice.

Extended Node Features:

Beyond the essential children and isEndOfWord, real-world trie nodes often include:

Word count: How many times was this word inserted? (for frequency tracking)
Prefix count: How many words pass through this node? (for prefix statistics)
Associated value: Store data associated with the complete word (dictionary definitions, scores, etc.)

production-trie-node.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/**
 * Production-Ready Trie Node with Extended Features
 * 
 * This template includes commonly needed features while
 * maintaining clean separation of concerns.
 * 
 * @template V - Type of value associated with complete words
 */
class TrieNode<V = void> {
    /**
     * Children mapping: character → child node
     * Use Map for Unicode support; switch to array for performance
     * with fixed alphabets
     */
    children: Map<string, TrieNode<V>>;
    
    /**
     * True if a complete word ends at this node
     * Required to distinguish words from prefixes
     */
    isEndOfWord: boolean;
    
    /**
     * Number of times this exact word was inserted
     * Useful for: frequency counting, duplicate detection
     * Only meaningful when isEndOfWord is true
     */
    wordCount: number;
    
    /**
     * Number of words that pass through this node (including as endpoint)
     * Useful for: prefix statistics, pruning decisions
     * Updated during insert/delete
     */
    passCount: number;
    
    /**
     * Optional value associated with this word
     * Only set when isEndOfWord is true
     * Useful for: dictionary entries, autocomplete metadata
     */
    value: V | undefined;
    
    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
        this.wordCount = 0;
        this.passCount = 0;
        this.value = undefined;
    }
    
    /**
     * Check if this node has any children
     * Useful for deletion logic
     */
    hasChildren(): boolean {
        return this.children.size > 0;
    }
    
    /**
     * Check if this node can be pruned
     * A node can be pruned if it's not a word ending
     * and has no other children
     */
    canPrune(): boolean {
        return !this.isEndOfWord && !this.hasChildren();
    }
    
    /**
     * Get child, creating if it doesn't exist
     * Simplifies insert logic
     */
    getOrCreateChild(char: string): TrieNode<V> {
        if (!this.children.has(char)) {
            this.children.set(char, new TrieNode<V>());
        }
        return this.children.get(char)!;
    }
}
 
/**
 * Trie with extended features
 */
class ProductionTrie<V = void> {
    private root: TrieNode<V>;
    private wordCount: number;
    
    constructor() {
        this.root = new TrieNode<V>();
        this.wordCount = 0;
    }
    
    /**
     * Insert a word with optional associated value
     */
    insert(word: string, value?: V): void {
        let current = this.root;
        current.passCount++;  // Root is passed by every word
        
        for (const char of word) {
            current = current.getOrCreateChild(char);
            current.passCount++;  // Track words passing through
        }
        
        if (!current.isEndOfWord) {
            this.wordCount++;  // New unique word
        }
        
        current.isEndOfWord = true;
        current.wordCount++;  // Track insertion frequency
        current.value = value;
    }
    
    /**
     * Count how many words start with this prefix
     */
    countPrefix(prefix: string): number {
        let current = this.root;
        
        for (const char of prefix) {
            if (!current.children.has(char)) {
                return 0;
            }
            current = current.children.get(char)!;
        }
        
        return current.passCount;
    }
    
    /**
     * Get word frequency (how many times it was inserted)
     */
    getFrequency(word: string): number {
        let current = this.root;
        
        for (const char of word) {
            if (!current.children.has(char)) {
                return 0;
            }
            current = current.children.get(char)!;
        }
        
        return current.isEndOfWord ? current.wordCount : 0;
    }
    
    /**
     * Get value associated with a word
     */
    getValue(word: string): V | undefined {
        let current = this.root;
        
        for (const char of word) {
            if (!current.children.has(char)) {
                return undefined;
            }
            current = current.children.get(char)!;
        }
        
        return current.isEndOfWord ? current.value : undefined;
    }
    
    /**
     * Total unique words in the trie
     */
    size(): number {
        return this.wordCount;
    }
}

Summary: The Trie Node Blueprint

We've thoroughly explored the anatomy of a trie node—the fundamental building block that makes prefix-based operations efficient. Let's consolidate the key insights:

Key Takeaways

•Two Essential Components: Every trie node needs children references (to navigate character-by-character) and an end-of-word flag (to distinguish complete words from mere prefixes).
•Children Storage Options: Arrays provide O(1) access for fixed alphabets; hash maps provide flexibility for variable or large character sets. The choice depends on your alphabet and sparsity.
•The End-of-Word Flag Is Non-Negotiable: Without it, you cannot correctly detect word existence when one word is a prefix of another. This is fundamental to trie semantics.
•Characters Belong to Edges, Not Nodes: The character that leads to a node is stored in the parent's children collection, not in the child node itself. This avoids duplication.
•Node Design Directly Enables Operations: Insert, search, prefix queries, and enumeration all rely on the interplay between children navigation and end-of-word marking.
•Extensions Are Common: Production tries often add word frequency, prefix counts, and associated values to nodes. These augmentations don't change the fundamental structure.

What's Next:

Now that you understand the basic node structure, the next page dives into alphabet size considerations—how the expected character set affects your design choices, memory usage, and performance characteristics. We'll explore why a 26-character English alphabet behaves very differently from a 65,536-character Unicode BMP.

Page Complete

You now have a deep understanding of trie node fundamentals. You can design nodes for specific use cases, implement the core structure in multiple languages, and understand how the node design enables trie operations. Next, we'll explore how alphabet size impacts these design decisions.