How to return an ArrayList with an recursive function

Question

I am new at java and i fight my way through... I have to do some homework and i resolve a lot from it, but at some points i dont know how to do it. My Problem: I must build some functions for a binary Tree (such as add nodes, count nodes, delete nodes, etc). Most of them i could find myself the algorithm. Now i struggle with a recursive method. I put commentaries into it to explain what my problem is:

    public List<E> getPreOrderList() {
    //TO DO:
    //this function should return  a list of the nodes in pre-order (value, left, right).
    //It must be implemented recursively!!!

    //THE PROBLEM:
    //If i create an ArrayList<E> inside the function, the 
    //recursion will generate each time a new ArrayList.
    //At the end i get as result an ArrayList with only one node.
    ArrayList<E> list = new ArrayList<E>();

    if (this.value == null) {
        return null;
    }
    //If I just print out the nodes, the pre-order algorithm is OK,
    //but i need to return all nodes into an ArrayList.
    System.out.print(value + ", ");
    list.add(value);
    if (left != null) {
        left.getPreOrderList();
    }
    if (right != null) {
        right.getPreOrderList();
    }
    return list;
}

Peter Lawrey · Accepted Answer · 2015-01-11 10:41:20Z

10

There is two way of doing this, simple but inefficient.

public List<E> getAll() {
     List<E> list = new ArrayList<>();
     if (value != null) list.add(value);
     if (left != null) list.addAll(left.getAll());
     if (right != null) list.addAll(right.getAll());
     return list;
}

This generates loads of lists and Object[] to hold them. A more efficient way is to provide a List to populate.

public List<E> getAll(List<E> list) {
     if (value != null) list.add(value);
     if (left != null) left.getAll(list);
     if (right != null) right.getAll(list);
     return list;
}

This creates far less objects (possibly none if the list has a large enough capacity)

answered Jan 11, 2015 at 10:41

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

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

Comments

Eran · Accepted Answer · 2015-01-11 10:46:26Z

5

You can pass the list to the recursive method. This way you only create the list once.

public List<E> getPreOrderList() {
    ArrayList<E> list = new ArrayList<E>();
    getPreOrderListRec(list);
    return list;
}

public void getPreOrderListRec(List<E> list) {
    // logic of recursive method, which add elements to the list
}

edited Jan 11, 2015 at 10:46

answered Jan 11, 2015 at 10:40

Eran

395k57 gold badges726 silver badges793 bronze badges

4 Comments

Peter Lawrey Over a year ago

Passing in a List is preferable for performance but not the only option. (A more functional approach is to treat arguments as immutable)

Marco13 Over a year ago

The internal implementation method (that receives the list as the argument) should be private.

Eran Over a year ago

@PeterLawrey Yes, that's not the only option.

chris1791 Over a year ago

@Eran + Marco13: Thanks a lot. This would be the right answer, but we had the condition: not use the last year solution. So i needed an alternative. So the solution is correct, but i cannot use it. I will try the solution of PeterLawrey tonight an give you guys an feedback.

Collectives™ on Stack Overflow

How to return an ArrayList with an recursive function

2 Answers 2

Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related