Можно в конец каждого слова добавить спецсимвол, который не может встретиться ни в каком слове (скажем, '$'). Тогда все слова будут гарантированно кончаться в листьях. При этом не нужно будет отмечать, какие промежуточные узлы являются концами слов, и алгоритмы слегка упрощаются.
Префиксное дерево (trie)