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);
}

Matthew Franglen Matthew Franglen · Accepted Answer · 2015-02-03T16:42:25

If your tree is balanced then it will be O(log n). This is because a balanced binary tree has twice as many nodes on each subsequent level, so if you double the quantity of nodes in the tree it only adds a single additional layer.

The path only holds the nodes that are parents of the current node, so it is not the case that you will end up holding the entire tree.

If your tree is completely unbalanced (i.e. every node has only a single child or less) then you will end up holding the entire tree in the list, as you must traverse every node in the tree to reach the single leaf. In this case it will be O(n).

Space complexity of printing all paths from root to leaf

3 Answers