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.