Java - tree data structure with multiple nodes - how to search efficiently

So far I do not know any Java built-in data structure that can handle what you are looking for. There are some tree implementations on github or this thread on stackoverflow will help you. But if I understood you right, you are also interested to have a well performing search on your tree. Sorting the tree does not completly solve this problem, because you still have to search every single subtree. Though it could significantly improve the search performance. But as far as I know there is no out of the box data structure in Java.

Another approach that came to my mind is to use a Map with your label and a reference to the according Node. However you would need a Tree where you can go from the leaves to the root node to get the full path and you have to take care of the duplicated information. E.g. if you delete a node, you also have to delete it in the map. If you also want to traversy the tree from the root you might build a bidirectional tree.

This is how my approach would look like:

class Node {
    String label;
    Node parent;
}

class Tree {
    HashMap<String, List<Node>> tree;
}

It is a List<Node> if you have multiple times the same label name. E.g. if you have necklaces at jewlery and summer collection

You need two things for this:

In your Node object, have a reference to the parent node as well:

class Node{
    String label;
    List<Node> children;
    Node parent;
}

Create a HashMap that maps labels to the nodes:

HashMap<String, Node> labelsToNodes;

Then searching is done with the get() method in the HashMap. You get your category list by repeatedly getting the parent nodes. Let me know if you'd like the code for this and I'll add it (I'm short on time right now).