Space complexity of printing all paths from root to leaf

Question

What is the space complexity of storing a path ie. nodes of a binary tree from root to a particular leaf in an array?

Basically, I am looking for space complexity of the following algorithm:

public void printPath () {
    doPrint(root, new ArrayList<TreeNode>());
}


private void doPrint(TreeNode node, List<TreeNode> path) {
    if (node == null) return;

    path.add(node);

    if (node.left == null && node.right == null) {
        System.out.println("Path from root: " + root.item + " to leaf: " + node.item + " - ");
        for (TreeNode treeNode : path) {
            System.out.print(treeNode.item + " ");
        }
        System.out.println();
    }

    doPrint(node.left , path);
    doPrint(node.right, path);

    path.remove(path.size() - 1);
}

Answer 1

You are storing the all the nodes that lie on the path from the root to a particular leaf in the List.

If the binary tree is height balanced or it is a full/complete binary tree, the worst case time and space complexity is O(log n), where n is the number of nodes in the binary tree.

If we do not have any prior information of the type of binary tree, then the worst case time and space complexity is O(n) since the tree can be of the form that there is only the left child present or only the right child present.