Can I use a trie that has a whole word on each node?

Question

I want to implement a trie to check for the validity of paths, so I would have a tree built that contains all the possible path constructions by breaking it down by directory. So something like /guest/friendsList/search would go from the root node to it's child guest, then guest's child friendsList, and then friendsList's child search. If search is a leaf node then my string /guest/friendsList/search would be considered valid.

Is this something a trie would be useful for. All the implementations of tries I've seen deal with individual letters at each node, but can they be whole strings instead? Is a trie specific to this kind of implementation and what I'm trying to do just a basic tree?

Thanks!

Answer 1

You can absolutely do this, though I'd typically call this a directory tree rather than a trie since you're essentially modeling the file system as a tree structure rather than storing lots of prefixes of different strings. In fact, the OS probably has a similar data structure on disk for representing the file system!

Answer 2

The directory tree can definitely do that. Creating a root node at first and then adding remaining directory entries to the root node as children, and so on. So checking if a path name is valid is just parsing the whole string and going through the directory tree.

If you want to make it faster, you can use a dictionary to store a level of nodes and searching a name is linear in one level. So searching a path name in the directory tree takes O(h), and h is the height of the directory tree. Further, to prevent redundant searching, keeping track of height of the directory tree can optimize the searching time; when the length of parsed path name exceeds the height, we know we do not need to search the directory tree.