Encoding feature with tree-path data
Clustering

I think a tree is a perfectly appropriate data structure in this case. You don't need an embedding to do clustering; there are similarity-based approaches too, and defining a similarity function in your case is straightforward: I'd say it's a function of the common depth between the two items in consideration. You will probably want to define a root to "normalize" the scores. For example, given the root "a/b/" and the paths:

a/b/c/d/foo1
a/b/c1/foo2
a/b/c1/foo3
a/b/c/d/foo4


The shared depth between foo1 and foo2 and 0, discounting the root. For foo1 and foo4 it is 2. For foo2 and foo3 it is 1. You can define the similarity as a transformation of this through the function $f:x \to 1-\exp(-ax)$, where $a$ is a parameter you can use to tweak the clusters.

For implementation, in python, you can try sklearn.

General

You can featurize a path string by creating a set from its parent folders, which can then be represented as a sparse bit string by hashing the set elements. For example, "a/b/c/d/foo1" becomes ("c", "c/d"), if we let "a/b" be the root, as before. (The notion of a root is not strictly necessary here except to ensure that the baseline similarity is zero.) The path similarity is simply then the set similarity or, after conversion to bit strings, the $L_p$ distance.