Creating a java hierarchial treeset from a flat list

Question

I have list of Objects T, it has a property of parent where the top objects parent property is null. I want to put all the objects into a TreeSet (or TreeMap). Top level objects will be all the root objects that has no parent (parent is null) and they will have their children under them.

Something like this

              o
           /  |   \
          Ra  Rb   Rc          -- Level Root Objects
         / |   \    | \
        Ca1 Ca2 Cb1 Cc1 Cc2    -- Level of First Children
     /   \
   Ca11   Ca12..............   -- Level of Second Children

So I can get Ra and find its children (Ca1, Ca2, Ca11, Ca12....)

Update: Sorry may be it wasn't clear, nodes point to parents and if parent is null, they are root nodes. The problem is parents need to know its children. But the relationship is in the opposite direction.

class Node
{
  private Node parent;
  private String name;
} 

Answer 1

I think you may be unclear about what a TreeSet does in Java. A TreeSet is simply an implementation of the Set interface, which uses a tree internally. Likewise for TreeMap. It's not a general purpose tree structure which allows you to traverse from parents to children. The fact that it uses trees is strictly a detail of the internal implementation.

I understand that you have a bunch of objects, each of which has a reference to a "parent" object. Those "parent" links form a tree, but you want to traverse from parents to children, and not the opposite direction (which would be easy).

In this case I would probably walk over the list of objects and build a Map from parent object to List of children. Something like:

Map<Node,List<Node>> tree  = new HashMap<Node,ArrayList<Node>>();
List<Node>           roots = new ArrayList<Node>();
for(Node n : nodes) {
  if(n.parent == null)
    roots.add(n);
  else {
    if(!tree.containsKey(n.parent))
      tree.put(n.parent, new ArrayList<Node>());
    tree.get(n.parent).add(n);
  }
}

Answer 2

Here is the solution I come up with

SortedSet<Node> nodeSet = new TreeSet<Node>(new Comparator<Node>() {
    public int compare(Node node1, Node node2) {

        if (node1.getParent() == null) {
            if (node2.getParent() == null) {
                return  node1.getId().compareTo(node2.getId());
            }
            return -1;
        }

        if (node2.getParent() == null) return 1;

        int parentCompare = node1.getParent().getId()
                .compareTo(node2.getParent().getId());

        if (parentCompare == 0)
            return node1.getId().compareTo(node2.getId());

        return parentCompare;
    }
});

nodeSet.addAll(allData); // allData is the Node list


Map<Node, List<Node>> map = new HashMap<Node, List<Node>>();

for(Node node : nodeSet)
{
    if(map.get(node)==null)
    {
        map.put(node, new ArrayList<Node>());
    }
    map.get(node).add(node);
    Node parentNode = node.getParent();
    while(parentNode!=null)
    {
        map.get(parentNode).add(node);
        parentNode = parentNode.getParent();
    }
}

// At this point I can get an element from map and see all children in values.