0

I have referred various resources but still have a doubt regarding tries.

  1. Do characters actually get stored in a trie? ( i think the answer is no)
  2. Suppose we are storing CAT and CAB in a trie. We need 2 separate nodes for the character B and T but I have a confusion regarding their address. Where will the pointer to the nodes of B and T be stored? root -> children[(indexOf)C] -> children[(indexOf)A] can only store one address so...?
0

The words are encoded in the path to a node (the indices in the various children arrays), the node (beyond an array of pointers to its children) only stores the information whether the path to it encodes an actual word (or it is only part of another). So CAT and CAB would result in a trie like

root node (empty string)
       not a word
           |
           | C
           v
         node1
       not a word
           |
           | A
           v
         node2
       not a word
       /        \
      / B      T \
    |_            _|
  node3          node4
is a word      is a word

(omitted entries with NULL pointers)

When testing a word, you follow the trie. If the path the word describes exists, and the node at that position says it's an actual word, you have found the entry. If path does not exist, or the node says it's not a word, it's not in the dictionary.

2
  • how will i follow the trie? where do the pointers to node4 and node3 get stored?
    – pj8126
    Feb 28 '18 at 17:04
  • Pointers to node3 and node4 are part of node2's children array. While walking the trie, you keep a pointer to the current node, and move it forward while you process the word character by character.
    – Blauelf
    Feb 28 '18 at 17:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .