Print all nodes from root to leaves

I've made a function to print all paths from root to all leaves in a binary search tree. I already have an insert function, which I haven't included in the code here as I felt it was irrelevant to the question. However, assume that it works. The code provided does produce the correct results. However, is it optimal? Is there room for improvement? Also, am I correct in thinking that the time complexity of this function is \$O(n)\$?

public static void printPaths(Node node,ArrayList path) {

    if(node == null) {

        return;
    }

    path.add(node.value);

    if(node.leftChild == null && node.rightChild == null) {

        System.out.println(path);
        return;

    } else {

        printPaths(node.leftChild,new ArrayList(path));
        printPaths(node.rightChild,new ArrayList(path));
    }      
}

public static void main(String[] args) {

    BST tree = new BST();

    tree.insertNode(20);
    tree.insertNode(8);
    tree.insertNode(22);
    tree.insertNode(12);
    tree.insertNode(10);
    tree.insertNode(14);
    tree.insertNode(4);

    ArrayList path = new ArrayList();

    printPaths(tree.root, path);

However, is it optimal?

I don't see wasted operations or opportunities to simplify the main logic itself.

However, "optimal" is a bit tricky term. To begin with, optimal in terms of what? In terms of readability, I think this is fine. In terms of performance, it's not great. Cloning the list of nodes for every path is not efficient. If performance is important to you, then you need to rethink that part. I can think of at least these alternative algorithms:

• Use a shared linked list passed down to all method calls, that grows and shrinks as you go deeper or come back higher in the tree. This will avoid the duplication of the entire path.

• Use a shared array list passed down to all method calls, and also pass the current depth n. In each method call, overwrite the n-th element, and print the list contents up until the n-th element. This will avoid the duplication of the entire path. For an extra boost, if you know in advance the depth of the tree, initialize the array list with a size big enough to contain the entire path, so it doesn't need to be resized along the way. In fact, instead of an array list, you could use a plain array for best performance.

Is there room for improvement?

Use interface types in method signatures and variable declarations. For example:

printPaths(Node node, List path) { ... }
List path = new ArrayList();

You can omit the return statement here:

if(node.leftChild == null && node.rightChild == null) {

    System.out.println(path);
    return;

} else {

    printPaths(node.leftChild,new ArrayList(path));
    printPaths(node.rightChild,new ArrayList(path));
}

And you should add a space in front of the opening paren of the if, and after commas in argument lists, like this:

if (node.leftChild == null && node.rightChild == null) {
    System.out.println(path);
} else {
    printPaths(node.leftChild, new ArrayList(path));
    printPaths(node.rightChild, new ArrayList(path));
}

Another alternative is to keep the return but drop the else:

if (node.leftChild == null && node.rightChild == null) {
    System.out.println(path);
    return;
}
printPaths(node.leftChild, new ArrayList(path));
printPaths(node.rightChild, new ArrayList(path));

Also, am I correct in thinking that the time complexity of this function is O(n)?

Yes. You visit all the n nodes exactly once.

Unfortunately, no, as @Florian explains very well in his answer.
You might want to consider accepting his answer instead.

StackExchange Code Review Q#63921, answer score: 4