Insert car, cart, cat, dog into an empty trie. Every node holds one character, so a path from the root spells a prefix, and words that start the same way will share nodes. The root holds nothing.
Inserting 4 words into an empty trie.
"car", letter 'c'. No child 'c' yet, so create one and step into it.
Create child c.
"car", letter 'a'. No child 'a' yet, so create one and step into it.
Create child a.
"car", letter 'r'. No child 'r' yet, so create one and step into it.
Create child r.
End of "car": mark this node terminal. Without the mark, a word that is only a prefix of another, or a prefix that is not a word, could not be told apart.
car stored.
"cart", letter 'c'. The current node already has a child 'c', shared with an earlier word, so follow it.
Follow existing child c.
"cart", letter 'a'. The current node already has a child 'a', shared with an earlier word, so follow it.
Follow existing child a.
"cart", letter 'r'. The current node already has a child 'r', shared with an earlier word, so follow it.
Follow existing child r.
"cart", letter 't'. No child 't' yet, so create one and step into it.
Create child t.
End of "cart": mark this node terminal. Without the mark, a word that is only a prefix of another, or a prefix that is not a word, could not be told apart.
cart stored.
"cat", letter 'c'. The current node already has a child 'c', shared with an earlier word, so follow it.
Follow existing child c.
"cat", letter 'a'. The current node already has a child 'a', shared with an earlier word, so follow it.
Follow existing child a.
"cat", letter 't'. No child 't' yet, so create one and step into it.
Create child t.
End of "cat": mark this node terminal. Without the mark, a word that is only a prefix of another, or a prefix that is not a word, could not be told apart.
cat stored.
"dog", letter 'd'. No child 'd' yet, so create one and step into it.
Create child d.
"dog", letter 'o'. No child 'o' yet, so create one and step into it.
Create child o.
"dog", letter 'g'. No child 'g' yet, so create one and step into it.
Create child g.
End of "dog": mark this node terminal. Without the mark, a word that is only a prefix of another, or a prefix that is not a word, could not be told apart.
dog stored.
4 words in 8 nodes. Shared prefixes are stored once, and every insert or lookup costs O(length of the word), whatever the number of words.
4 words stored in 8 nodes.