sort arraylist into tree recursively

Question

I have an arraylist of Object. But I need a tree with the following parameters:

1. Some Objects are not supposed to have children (non-category objects)
2. Category Objects are supposed to have children (which can be additional category objects, or non-category objects)
3. Category objects that have no children should be skipped/removed

All objects have a variable for what their parent is. But I don't have a good algorithm that can recursively determine how many children each category object has. All children on the same level will be an ArrayList<Object>

I currently have an iterative method that can only go one level deep, and cannot distinguish some versions of scenario 2. I don't think it's code is relevant because it is not recursive.

insight appreciated

Answer 1

Use the Composite Pattern to provide a common interface for all your objects.

An interface or abstract superclass, the Component, represents all objects that may have a relationship. One subclass, the Leaf, doesn't have any children. (There could be other non-composite Leaf-like subclasses.) Another subclass, the Composite, contains many objects, generally of any kind of Component. That allows the Composite to contain other Composites, or other non-composites such as Leaf.

The Component superclass I'm creating here is ComponentObject. Here, all ComponentObjects have a parent, the CategoryObject, which is introduced below.

ComponentObject

public abstract class ComponentObject
{
   private CategoryObject myParent;

   protected ComponentObject(CategoryObject parent)
   {
      myParent = parent;
   }

   public CategoryObject getParent()
   {
      return myParent;
   }

   public abstract int getNumChildren();
}

It has two concrete subclasses, NonCategoryObject, the Leaf which cannot contain children, and CategoryObject, the Composite which encapsulates a list of children objects, which can be either other CategoryObjects or NonCategoryObjects.

NonCategoryObject

public class NonCategoryObject extends ComponentObject
{
   public NonCategoryObject(CategoryObject parent)
   {
      super(parent);
   }

   @Override
   public int getNumChildren()
   {
      return 0;
   }
}

CategoryObject

public class CategoryObject extends ComponentObject
{
   private ArrayList<ComponentObject> myChildren;

   public CategoryObject(CategoryObject parent)
   {
      super(parent);
      myChildren = new ArrayList<ComponentObject>();
   }

   public void addChild(ComponentObject child)
   {
      myChildren.add(child);
   }

   public ComponentObject getChild(int index)
   {
      return myChildren.get(index);
   }

   public int getNumDirectChildren()
   {
      return myChildren.size();
   }

   @Override
   public int getNumChildren()
   {
      int numChildren = 0;
      for (ComponentObject child : myChildren)
      {
         // One for the child itself, plus add any of the child's children.
         numChildren += 1 + child.getNumChildren();
      }
      return numChildren;
   }
}

The "getNumChildren" method is important for finding the number of children via the Composite Pattern.

Setting Up the Data

You have an ArrayList of components, each of which knows their parent, but not who their children are:

public static void main(String[] args)
{
   // Create a tree structure, parent information only.
   CategoryObject root = new CategoryObject(null);
   CategoryObject categoryOne = new CategoryObject(root);
   CategoryObject categoryTwo = new CategoryObject(root);
   CategoryObject categoryThree = new CategoryObject(root);
   CategoryObject categoryOneOne = new CategoryObject(categoryOne);
   CategoryObject categoryOneTwo = new CategoryObject(categoryOne);
   CategoryObject categoryOneThree = new CategoryObject(categoryOne);
   NonCategoryObject leafOneFour = new NonCategoryObject(categoryOne);
   NonCategoryObject leafOneOneOne = new NonCategoryObject(categoryOneOne);
   NonCategoryObject leafOneOneTwo = new NonCategoryObject(categoryOneTwo);
   NonCategoryObject leafOneTwoOne  = new NonCategoryObject(categoryOneTwo);
   NonCategoryObject leafOneThreeOne  = new NonCategoryObject(categoryOneThree);
   NonCategoryObject leafTwoOne = new NonCategoryObject(categoryTwo);
   NonCategoryObject leafThreeOne = new NonCategoryObject(categoryThree);

   // We're given the ArrayList
   ArrayList<ComponentObject> components = new ArrayList<ComponentObject>();
   // The order doesn't matter.
   components.addAll(Arrays.asList(leafOneFour, leafOneOneTwo, leafOneThreeOne,
      categoryOne, categoryOneOne, categoryOneThree, root, leafThreeOne,
      leafOneOneOne, categoryThree, leafOneTwoOne, leafTwoOne,
      categoryTwo, categoryOneTwo));

Determine child information by looping over the list. We'll also find the root (assuming there's only one parent-less component).

   ComponentObject foundRoot = null;
   for (ComponentObject c : components)
   {
      CategoryObject parent = c.getParent();
      if (parent == null)
      {
         foundRoot = c;
      }
      else
      {
         parent.addChild(c);
      }
   }

Now all parents know who their children are. Next, we'll call 2 different methods, each with their own way of determining the number of children:

   // 2 methods to determine the number of children.
   compositeMethod(foundRoot);
   recursiveMethod(foundRoot);
}

The Methods

Here are the methods. First, the "composite" method, which takes advantage of the composite pattern to determine the number of children. It simply calls the root's getNumChildren() method.

private static void compositeMethod(ComponentObject root)
{
   int numChildren = root.getNumChildren();
   System.out.println("Composite method: " + numChildren);
}

Output:

Composite method: 13

The composite method isn't quite recursive, because even though it calls itself, the object on which it calls itself is different. It calls itself on the object's children.

The recursive method, which you are interested in, calls itself at each level in the hierarchy:

private static void recursiveMethod(ComponentObject root)
{
   int numChildren = findNumChildren(root);
   System.out.println("Recursive method: " + numChildren);
}

// The actual recursive method.
private static int findNumChildren(ComponentObject root)
{
   if (root instanceof CategoryObject)
   {
      CategoryObject parent = (CategoryObject) root;
      int numChildren = 0;
      for (int i = 0; i < parent.getNumDirectChildren(); i++)
      {
         ComponentObject child = parent.getChild(i);
         // One for the child itself, plus its children.
         numChildren += 1 + findNumChildren(child);
      }
      return numChildren;
   }

   // Base case: NonCategoryObjects have no children.
   return 0;
}

Output:

Recursive method: 13

Answer 2

Since I often use tree structures like the one you describe, I created a dummy implementation some time ago. I changed the code a bit to make it more general and updated it to your needs, feel free to make good use of it as you see fit.

The "id" of the tree elements is generic, so you can use any data as ids for the elements. An example usage is documented inside the main method that creates some random tree structure. Once a tree is generated you can then validate and navigate the tree using the Visitor pattern.

Here is the code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;

public class TestStructure {

public interface ElementVisitor<E>{
    boolean startVisit(Element<E> e);
    void endVisit(Element<E> e);
}

public interface Element<E>{
    E getId();
    public boolean isParent();
    Parent<E> getParent();
    void visit(ElementVisitor<E> visitor);
}

public interface Parent<E> extends Element<E>{
    List<Element<E>> getChildren();
    int size();
}

public static abstract class ElementImpl<E> implements Element<E>{
    private final E id;
    private ParentImpl<E> parent;

    public ElementImpl(E id) {
        super();
        if (id == null) {
            throw new IllegalArgumentException("id must not be null");
        }
        this.id = id;
    }

    void setParent(ParentImpl<E> parent) {
        this.parent = parent;
    }
    @Override
    public final ParentImpl<E> getParent() {
        return parent;
    }
    protected final void addToParent(){
        parent.addChild(this);
    }
    protected final void removeFromParent(){
        parent.removeChild(this);
    }
    public final boolean isTreeRoot(){
        return parent == null;
    }

    @Override
    public String toString() {
        return getId().toString();
    }

    public int getTreeLevel() {
        int level = 0;
        ParentImpl<E> parent = this.parent;
        while (parent != null) {
            parent = parent.getParent();
            level++;
        }
        return level;
    }

    public ParentImpl<E> getRoot(){
        ElementImpl<E> e = this;
        while (e.parent != null) {
            e = e.parent;
        }
        return (ParentImpl<E>) e;
    }

    public E getId() {
        return id;
    }
}

public static class ChildImpl<E> extends ElementImpl<E> implements Element<E>{

    public ChildImpl(E id) {
        super(id);
    }

    @Override
    public void visit(ElementVisitor<E> visitor) {
        visitor.startVisit(this);
        visitor.endVisit(this);
    }

    @Override
    void setParent(ParentImpl<E> parent) {
        super.setParent(parent);
        // add childs to parent automatically
        addToParent();
    }
    @Override
    public boolean isParent() {
        return false;
    }
}

public static class ParentImpl<E> extends ElementImpl<E> implements Parent<E>{
    private List<ElementImpl<E>> children;
    boolean added = false;

    public ParentImpl(E id) {
        super(id);
    }

    @SuppressWarnings("unchecked")
    @Override
    public List<Element<E>> getChildren() {
        return children == null ? Collections.EMPTY_LIST : children;
    }

    public void addChild(ElementImpl<E> child){
        if (children == null) {
            children = new ArrayList<>();
        }
        if (getParent() != null && children.size() == 0) {
            // only include parents in the tree if they have children
            addToParent();
            added = true;
        }
        children.add(child);
    }

    public boolean removeChild(ElementImpl<E> e) {
        if (children != null && children.remove(e)) {
            if (children.size() == 0) {
                children = null;
                removeFromParent();
                added = false;
            }
        }
        return false;
    }

    @Override
    void setParent(ParentImpl<E> parent) {
        super.setParent(parent);
        if (children != null && !added) {
            addToParent();
            added = true;
        }
    }

    @Override
    public int size() {
        return children == null ? 0 : children.size();
    }

    @Override
    public void visit(ElementVisitor<E> visitor) {
        if (visitor.startVisit(this)) {
            for (Element<E> e : getChildren()) {
                e.visit(visitor);
            }
        }
        visitor.endVisit(this);
    }

    @Override
    public boolean isParent() {
        return true;
    }

}


public static void main(String[] args) {

    // elements below parentRange are considered parents
    int parentRange = 80;

    // The number of all elements in the tree
    int numberOfElements = 150;

    Map<Integer, Integer> relationMap = new HashMap<>(); // map from child id to parent id
    Random random = new Random();

    // id 0 == root id
    // create an initial parent element at the root
    relationMap.put(1, 0);
    // create the parent elements
    for (int id = 2; id < parentRange; id++) {
        int parentId = random.nextInt(id-1);
        relationMap.put(id, parentId);
    }

    // create the child elements
    for (int id = parentRange; id < numberOfElements; id++) {
        int parentId = random.nextInt(parentRange);
        relationMap.put(id, parentId);
    }

    HashMap<Integer, ParentImpl<Integer>> map = new HashMap<>();

    final ParentImpl<Integer> treeRoot = new ParentImpl<>(0);
    map.put(0, treeRoot);
    // create the tree structure
    for (Entry<Integer, Integer> entry : relationMap.entrySet()) {
        Integer childId = entry.getKey();
        Integer parentId = entry.getValue();

        ParentImpl<Integer> parentImpl = map.get(parentId);
        if (parentImpl == null) {
            parentImpl = new ParentImpl<>(parentId);
            map.put(parentId, parentImpl);
        }

        ElementImpl<Integer> child;
        if (childId < parentRange) {
            // this child is a parent
            child = map.get(childId);
            if (child == null) {
                ParentImpl<Integer> p = new ParentImpl<>(childId);
                child = p;
                map.put(childId, p);
            }
        } else{
            child = new ChildImpl<>(childId);
        }
        child.setParent(parentImpl);

    }

    // count the number of elements in the tree
    class Counter  implements ElementVisitor<Integer> {
        int count = 0;
        @Override
        public boolean startVisit(Element<Integer> e) {
            count++;
            return true;
        }
        @Override
        public void endVisit(Element<Integer> e) {}
    };

    Counter counter = new Counter();
    treeRoot.visit(counter);
    System.out.println("Number of all elements in the tree: " + counter.count);

    // validate the tree structure
    ElementVisitor<Integer> treeValidator = new ElementVisitor<Integer>() {
        @Override
        public boolean startVisit(Element<Integer> e) {
            if (!e.getId().equals(0) && e.getParent() == null) {
                throw new IllegalStateException("child with no parent...");
            }
            if (e.isParent()) {
                Parent<Integer> parent = (Parent<Integer>)e;
                if (parent.size() == 0) {
                    throw new IllegalStateException("parent with no children...");
                }
            }
            return true;
        }

        @Override
        public void endVisit(Element<Integer> e) {}
    };
    treeRoot.visit(treeValidator);

    final StringBuilder b = new StringBuilder();
    // print the tree structure
    ElementVisitor<Integer> treePrinter = new ElementVisitor<Integer>() {
        int level = 0;
        @Override
        public boolean startVisit(Element<Integer> e) {
            for (int i = 0; i < level; i++) {
                b.append("  ");
            }
            if (e.isParent()) {
                b.append("Parent ");
                level++;
            } else{
                b.append("Child ");
            }
            b.append(e.getId());
            b.append('\n');
            return true;
        }

        @Override
        public void endVisit(Element<Integer> e) {
            if (e.isParent()) {
                level--;
            }
        }
    };
    treeRoot.visit(treePrinter);
    System.out.println("The generated tree structure: ");
    System.out.println(b.toString());
}
}

Answer 3

I faced a similar problem but in Javascript. Someone answered it for me with a recursive algorithm here:

Convert parent-child array to tree

It might not be perfect as-is but hopefully it will give you a starting point.