How exactly does return statement work in recursive function?

I’m having a hard time approaching any binary tree questions and most of them are recursive, so I decided to detour and start from the basics again. This is basically the pre-order traversal list. I’ve identified two ways that can give me the correct results if there is at least 1 node, but I’m unsure about the intrinsic differences between the two. As you can see, one returns the list when encounter null, the other returns null when encounter null:

public List<Integer> getList1(TreeNode root) {
    return getList1Helper(root, new ArrayList<>());
}

private List<Integer> getList1Helper(TreeNode root, List<Integer> list) {
    if (root == null) {
        return list;
    }
    list.add(root.val);
    getList1Helper(root.left, list);
    getList1Helper(root.right, list);
    return list;
}

public List<Integer> getList2(TreeNode root) {
    return getList2Helper(root, new ArrayList<>());
}

private List<Integer> getList2Helper(TreeNode root, List<Integer> list) {
    if (root == null) {
        return null; // difference denoted *
    }
    list.add(root.val);
    getList2Helper(root.left, list);
    getList2Helper(root.right, list);
    return list;
}

Does anybody have any ideas about it? Also, why doesn’t the function return the list and stop all recursions when hitting the first null?

Answer

Although you return something different in the two versions of the code, neither helper functions actually use the value returned from a recursive call:

getList2Helper(root.left, list);

The above makes the recursive call, which returns something, but the caller does not do anything with it.

The only time there is a difference in the returned value, is when the base case kicks in. That means that there is a difference for the initial caller when they pass null as first argument (denoting an empty tree). The first version will return an empty array list, while the second will return null. So they are not completely equivalent. The one that returns the array list would be more what I would expect to get back for an empty tree (i.e. an empty array list, not null).

Cleaning up

As the helper function actually populates the array list that is given as argument, it should not need to return anything. The main function could create the array list, pass it to the helper (which returns nothing) and then return that populated list.

Like this:

public List<Integer> getList(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    getListHelper(root, list);
    return list;
}

private void getListHelper(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    getListHelper(root.left, list);
    getListHelper(root.right, list);
}

Alternative

You could avoid to have the helper function (with its second parameter) at all, and instead populate a local array list from the lists that the recursive calls return:

public List<Integer> getList(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root != null) {
        list.add(root.val);
        list.addAll(getList(root.left));
        list.addAll(getList(root.right));
    }
    return list;
}

This is less efficient, as values get copied from one list to another several times. With a linked list implementation that would allow to concatenate lists in O(1) time, you could overcome that downside.