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;
}

Solution 1

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)

Solution 2

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
}

Comments

[Vishy]

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

[Marco13]

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

[Eran]

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

[chris1791]

@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.