Does Trie Node store the character value?

Question

I am learning Trie and get a bit confused from the description in wikipedia: http://en.wikipedia.org/wiki/Trie

It appears in the example picture that the characters are stored in both the node and edge? What's the most common implementation of the node class? Do people usually store the character in the node object? Or do they usually store it with the edge?

thanks!

Answer 1

Characters need to at least be stored on the edge (well, as a technicality, I'm not sure whether I'd classify it as being stored on the edge, but rather on the parent).

The reasoning behind this - How will you efficiently find a string in the tree if you don't know what characters the children represents? At each level, you'll have to look through all the children:

for each child c
  if c.char == character we're looking for

instead of just: (assume children is a Map of Character to Node)

children.get(character we're looking for)

You can of course 'store' the character more compactly - if you have only lower-case characters, you can just have an array - Node children[26], where you'd do look-ups like:

children[character we're looking for - 'a']

meaning children[0] would be the child for 'a', children[1] the child for 'b', etc.

Answer 2

I think an edge makes more sense when you have a 2d array or a matrix. It can be complicated to build a tree and store value in edges.