print all root to leaf paths in a binary tree

Question

i am trying to print all root to leaf paths in a binary tree using java.

public void printAllRootToLeafPaths(Node node,ArrayList path) 
{
    if(node==null)
    {
        return;
    }
    path.add(node.data);

    if(node.left==null && node.right==null)
    {
        System.out.println(path);
        return;
    }
    else
    {
        printAllRootToLeafPaths(node.left,path);
        printAllRootToLeafPaths(node.right,path);
    }      
}

In main method:

 bst.printAllRootToLeafPaths(root, new ArrayList());

But its giving wrong output.

given tree:

   5
  / \
 /   \
1     8
 \    /\
  \  /  \
  3  6   9

Expected output:

[5, 1, 3]

[5, 8, 6]

[5, 8, 9]

But the output produced:

[5, 1, 3]

[5, 1, 3, 8, 6]

[5, 1, 3, 8, 6, 9]

Can some one figure it out...

Answer 1

Call the recursive methods with:

printAllRootToLeafPaths(node.left, new ArrayList(path));
printAllRootToLeafPaths(node.right, new ArrayList(path));

What happens there when you pass the path (instead of new ArrayList(path) is that you use a single object in all methods call, which means that, when you return to the original caller, the object is not in the same state as it was.

You just need to create a new object and initialize it to the original values. This way the original object does not get modified.