A trie node typically contains: class TrieNode: children: map from char to TrieNode isEndOfWord: boolean For lowercase English letters, you can use an array of 26 instead of a map: class TrieNode: children: array of 26 TrieNodes (initially null) isEndOfWord: boolean The isEndOfWord flag marks whether a complete word ends at this node.
Without it, you couldn't distinguish between "car" and "card" if both are in the trie. The path c→a→r exists for both.
Space complexity: where is number of words and is average length. In practice, prefix sharing reduces this significantly. Time: . Space: .