Why does each node in this Trie contain a linked list?

Question

For my class project I have to construct a Trie. My professor insists that each node contain a linked list, but I do not understand why. Why can I not just put a linked list in the root? Wouldn't putting a linked list in each node be redundant? Also, how many nodes do I put in each node's linked list?

My professor would like to see the following fields in our node constructor:

(1) A leading character (possibly empty (for root))

(2) String Label (possibly null (for root))

(3) Boolean IsWord , indicating whether the current node represents a whole word or not (this is helpful when one word may be a prefix of another).

(4) Node *RightSIbling

(5) Node *FirstChild

Also, I am well aware that there are other viable Trie implementations that do not require a linked list, but my professor insists we learn this specific method first.

Answer 1

A trie is essentially two linked lists. A (vertical) link to it's left-most child and a (horizontal) link to it's right sibling. The order of the sibling list is alphabetical, so you can search.

Words: as, at, and

Trie:

   a
 / | \
s  t  n
      |
      d

Using your structure:

Root node:

Node {
char:           a
isWord:         false
rightSibling:   null
firstChild:     Node[s]
}

Root's first (left-most) child:

Node {
char:           s
isWord:         true
rightSibling:   Node[t]
firstChild:     null
}

Node[s]'s right sibling

Node {
char:           t
isWord:         true
rightSibling:   Node[n]
firstChild:     null
}

Node[t]'s right sibling

Node {
char:           n
isWord:         false
rightSibling:   Node[n]
firstChild:     Node[d]
}

Node[n]'s first child:

Node {
char:           d
isWord:         true
rightSibling:   null
firstChild:     null
}