4
\$\begingroup\$

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<Integer> 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<Integer>(path));
        printPaths(node.rightChild,new ArrayList<Integer>(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<Integer> path = new ArrayList<Integer>();

    printPaths(tree.root, path);
\$\endgroup\$
  • \$\begingroup\$ Shouldn't you be removing elements from the path? \$\endgroup\$ – mjolka Sep 26 '14 at 7:40
  • 1
    \$\begingroup\$ @mjolka No, it seems a new copy of the path is made in each recursive call. \$\endgroup\$ – Florian F Sep 27 '14 at 12:56
  • \$\begingroup\$ @B.oof I was wrong about the \$O(n)\$ calculation, see my updated answer, and Florian's answer. You might want to consider accepting his answer instead of mine. \$\endgroup\$ – janos Sep 27 '14 at 20:02
4
\$\begingroup\$

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:

  1. 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.
  2. 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<Integer> path) { ... }
List<Integer> path = new ArrayList<Integer>();

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<Integer>(path));
    printPaths(node.rightChild,new ArrayList<Integer>(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<Integer>(path));
    printPaths(node.rightChild, new ArrayList<Integer>(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<Integer>(path));
printPaths(node.rightChild, new ArrayList<Integer>(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.

\$\endgroup\$
  • \$\begingroup\$ "You should add a space" should be "you could add a space". I, for instance, prefer the style "if( expression ){". \$\endgroup\$ – Florian F Sep 27 '14 at 13:01
  • \$\begingroup\$ @FlorianF This is the recommended style for the placement of spaces in both Eclipse and IntelliJ. If you want your code to be read by the widest possible audience, I think this is the style to go for. On the other hand I saw your answer about the complexity, it's spot on, and I updated my answer accordingly, pointing to yours. \$\endgroup\$ – janos Sep 27 '14 at 20:06
3
\$\begingroup\$

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

It would be O(n) if not for the fact that you make a fresh copy of the path in every recursive call. The length of the path is O(log n) on average, O(n) in the worst case. So, the cost of copying the path overall is O(n log n) on average and O(n^2) worst case.

Janos explains what you can do about it in his answer.

And strictly speaking, printing the output is part of the method. And the length of the output is already O(n log n) on average. So you need O(n log n) just to print the output. Generally, if whatever you do with the path at a leave is O(path.length) it brings your time performance down to O(n log n).

\$\endgroup\$
2
\$\begingroup\$

I'm annoyed that you pass an empty ArrayList<T> in your method. I think you should split your method in two. One that is parameterless, and public, to start the recursive algorithm, and another, internal(from C#) that has the parameter for the recursive algorithm. Also, maybe it's a convention in Java (I'm not very used to Java), but I think you should remove some white lines, it would make your code more concise.

public static void printPaths(Node node) {
    ArrayList<Integer> path = new ArrayList<Integer>();
    printPathsRecursive(node,path);
}

static void printPathsRecursive(Node node,ArrayList<Integer> 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<Integer>(path));
        printPaths(node.rightChild,new ArrayList<Integer>(path));
    }      
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.