trie iteration should include root?

Question

I'm working on a trie data structure. My simple, initial understanding: trie data structures require a fixed root node. This node cannot be deleted.

When iterating through all nodes in a trie (in pre-order), should the root node be reported included?

Should the "size" of the trie include the root node? It seems that it should match the number of items returned when iterating.

Maybe trie size and iterators should only reflect the leaf nodes? Is there any point in iterating through all the interior nodes?

Maybe my trie should start out truly empty? I can allow you to insert, modify, delete the root node?

Answer 1

A trie is a data structure where:

• nodes represent strings that are matched,
• edges represent transitions of one node to the next based on a given additional character, and
• the root node corresponds to the empty string that is always a matched when no characters are yet processed .

Based on this understanding, and from a theoretical point of view:

• root is a node like any other. It just correspond to a special extreme situation (i.e.string of length 0 reached when 0 chars are processed).
• the depth of a node corresponds to the number of edges traversed, so in principle to the length of the string.
• counting the number of nodes, means counting how many different strings can be identified by the trie. The empty root is just a special string in that set.
• iterating across the trie, means iterating through all strings that the trie is able to match. Again, recognizing as little as nothing - the root node - is just a special case.

If you think that the users of your trie are not interested in the empty string, nothing prevents you from ignoring it. However, it is an arbitrary decision based on your application domain and not on the trie's intrinsic structure. (Joke: it's as arbitrary as starting indexing arrays from 1 ;-)).