1

I need to return list of all the children after a particular node. Here is what i have done -

public List<Object> getChildrenTree(Object currentObject, List<Object> returnList){

        //get all child-URIs for the category
        List<Object> objectChildren = currentObject.getChildren();

        for (Obj childObj : objectChildren) {

            if(childObj !=null){

                if(childObj.getChildren().size() >0){
                    getChildrenTree(childObj,returnList);
                }else{
                    returnList.add(childObj);
                }
            }
        }

        return returnList;
    }

but it doesn't work and does not add all the children properly.

4 Answers 4

3

You are not adding children that have children.

You need to change your loop to :

    for (Obj childObj : objectChildren) {
        if(childObj !=null){
            returnList.add(childObj);
            if(childObj.getChildren().size() >0){
                getChildrenTree(childObj,returnList);
            }               
        }
    }
    return returnList;

i.e. you should always add childObj, regardless of whether or not it has children.

I also moved the addition of childObj to be before adding its children, assuming that's the order you wish the nodes to appear (i.e. first the parent, and then the children).

In addition, as sayed mentioned, there shouldn't be a return statement inside the loop, since it will skip adding all but the first child. The return statement should be after the loop.

Sign up to request clarification or add additional context in comments.

4 Comments

Thanks Eran. It still has a bug. I am not whats wrong with it but it still does not add all the children to the list.
it only returns the list of children for the first element.
can you please edit your answer a bit and i'll accept it. So, the problem was the return statement before the method call. It will make the method return only the children of first child.
@sayed Oh, I totally missed that. Thanks. I'll edit my answer.
1

You don't need one extra list that contains returning objects if your method is already returning it. Still you want then you can use it. Otherwise below code changes for your if will work fine.

     public List<Object> getChildrenTree(Object currentObject){

                    //get all child-URIs for the category
                    List<Object> returnList=new ArrayList<Object>();
                    List<Object> objectChildren = currentObject.getChildren();

                    for (Object childObj : objectChildren) {

                        if(childObj !=null){
                // add current child
                            returnList.add(childObj);
           if(!childObj.getChildren().isEmpty()){
            // invoke recursive to extract childs of current  object and add them to list. 
//That's all childs you need
                            returnList.addAll(getChildrenTree(childObj));
             }
                        }
                    }

                    return returnList;
                }

What you need just add current not-null childs and for all childs invoke same method to extract their childs and addAll to same list

3 Comments

Wont it create a new list every time the method is being called during recursion ? so we'll lose track of all the previous elements ??
Yes, this creates a new list for every level in the tree.
you will not lose anything because at one end your method holds all the elements. If you see first execution of method keeps all the returned elements from other calls.
0

You do not add the head node:

  public List<Object> getChildrenTree(Object currentObject, List<Object> returnList){

    returnList.add(currentObject);
    //get all child-URIs for the category
    List<Object> objectChildren = currentObject.getChildren();

    for (Obj childObj : objectChildren) {
        if(childObj !=null){
            if(childObj.getChildren().size() >0){
                return getChildrenTree(childObj,returnList);
            }               
        }
    }

    return returnList;
}

Comments

0

Nothing wrong with the answers given, but I thought I'd give a slight variation. I prefer to avoid the conditionals inside the loop if possible, which you can with some slight rearranging of the code. In the following example, I show both a Java 8 lambda version and a pre-Java 8. In this case, the Java 8 code doesn't really buy you anything, but I threw it in there anyway.

I created a custom Node class in order to see output

public class ListAdd {

    public static void main(String[] args) {
        Node node = new Node(0);
        addChildren(3,node);
        addChildren(4,node.getChildren().get(0));
        addChildren(2,node.getChildren().get(2));
        addChildren(1,node.getChildren().get(2).getChildren().get(0));
        addChildren(2,node.getChildren().get(2).getChildren().get(0).getChildren().get(0));

        List<Node> allNodes = getAllNodes(node,new ArrayList<>());
        System.out.println("------------------------\nTotal number of nodes:  " + allNodes.size());
        allNodes.forEach(System.out::println);

        allNodes = getAllNodesOld(node, new ArrayList<>());
        System.out.println("------------------------\nTotal number of nodes:  " + allNodes.size());
        allNodes.forEach(System.out::println);
    }

    public static List<Node> getAllNodes(Node parent, List<Node> allNodes){
        if(parent == null || parent.getChildren().size() < 1){
            return allNodes;
        }
        parent.getChildren()
          .forEach(node -> {
             allNodes.add(node); 
             getAllNodes(node,allNodes);
          });
        return allNodes;
    }

    public static List<Node> getAllNodesOld(Node parent, List<Node> allNodes){
        if(parent == null || parent.getChildren().size() < 1){
            return allNodes;
        }

        for(Node node : parent.getChildren()){
            allNodes.add(node);
            getAllNodesOld(node, allNodes);
        }
        return allNodes;
    }

    public static void addChildren(int amount, Node parent){
        for(int i=0;i<amount;i++){
            parent.addChild(new Node(i + (parent.getVal() + 1)));
        }
    }

    public static class Node{
        List<Node> children = new ArrayList<>();
        int val;

        public Node(int v){
            val = v;
        }

        public void addChild(Node node){
            children.add(node);
        }

        public List<Node> getChildren(){
            return children;
        }

        public int hashCode(){
            return 31 * val * (children.size() + 1);
        }

        public int getVal(){
            return val;
        }

        public boolean equals(Object o){
            if(o == this) return true;
            if(!(o instanceof Node)) return false;
            Node n = (Node)o;
            return val == n.val && children.containsAll(n.children);
        }

        public String toString(){
            return "Node{val="+val+",children="+children+"}";
        }
    }
}

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.