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

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;
    }
}

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

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"]

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;
    }
}