What's the best way to recursively traverse a BinaryTree in Java without void methods?

Question

Learning about binary Trees through a MOOC right now and I want to recursively traverse the tree and add data to a List but the assignment i'm working on doesn't want the method types to be changed. I know with a void method I could just do something like:

public static void preorder(TreeNode<T> root) {
    List<T> listOfData = new ArrayList<>();

    if (root == null) {
        return;
    }
 
   
    listOfData.add(root.getData());
 
    // Traverse the left subtree
    preorder(root.getLeft());
 
    // Traverse the right subtree
    preorder(root.right);
}

but right now my method is

public List<T> preorder(TreeNode<T> root) {
    List<T> listOfData = new ArrayList<>();

    if (root != null) {
        listOfData.add(root.getData());
        preorder(root.getLeft());
        preorder(root.getRight());
    }

     return listOfData;
}

doesn't appear that the list is updating per stack call beyond the initial return.

Answer 1

I know with a void method I could just do something like: [...]

The void function you presented doesn't do the job: the caller has no access to the local array list. Each call of this function creates a local list with at most one member, and when it returns that list is no longer accessible and flagged for garbage collection.

You're asking to get the function working without void return type (as stated in the title), but it is true that in your attempt you're only returning a list with again at most one member.

The problem is that your code ignores the lists that are returned by the recursive calls, yet that is the only information they give you. If you ignore that, you might as well not make those calls at all. They do work for nothing.

Here is the correction of your attempt:

public List<T> preorder(TreeNode<T> root) {
    List<T> listOfData = new ArrayList<>();
    if (root != null) {
        listOfData.add(root.getData());
        listOfData.addAll(preorder(root.getLeft() ));
        listOfData.addAll(preorder(root.getRight()));
    }
    return listOfData;
}