Я пытаюсь распечатать все пути от корня к листу в двоичном дереве, используя 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);
    }      
}

В основном методе:

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

Но это дает неправильный вывод.

данное дерево:

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

Ожидаемый результат:

[5, 1, 3]

[5, 8, 6]

[5, 8, 9]

Но на выходе получается:

[5, 1, 3]

[5, 1, 3, 8, 6]

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

Может кто-нибудь понять это ...