I read about TRIE data-structure and is slightly confused about detecting end-of-word. Why do we create another node to detect end-of-word? why cant same node be used it. For example, we have to construct a TRIE for word CAT. Now, as per specification, there will be 4 nodes; in which last node will contain a field


which will return true in this case. I am unable to understand why we couldn't use the third node "T" and return true from there.

  • $\begingroup$ How would you distinguish CA from CAT? What if your list of words contained both? What if it didn't? $\endgroup$ – Yuval Filmus Nov 5 '16 at 12:30
  • $\begingroup$ @YuvalFilmus if my list of words will contain both then, node containing A and T; both will return true. The reason is search input is given by user and that decides whether to include CA or CAT. Am i missing something here? $\endgroup$ – Prateek Jain Nov 5 '16 at 12:39
  • $\begingroup$ Tries as defined in Wikipedia don't have dummy nodes, but they still have an end-of-word mechanism (implemented differently). $\endgroup$ – Yuval Filmus Nov 5 '16 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.