How to Compute Space Complexity for Printing All paths which Sum to a Given Value in Binary Tree

Question

This problem is from the book Cracking the Coding Interview, and I have trouble understanding the space complexity specified for their solution.

Problem: You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. Note that a path can start or end anywhere in the tree.

Solution (in Java):

public static void findSum(TreeNode node, int sum, int[] path, int level) {
    if (node == null) {
        return;
    }

    /* Insert current node into path */
    path[level] = node.data; 

    int t = 0;
    for (int i = level; i >= 0; i--){
        t += path[i];
        if (t == sum) {
            print(path, i, level);
        }
    }

    findSum(node.left, sum, path, level + 1);
    findSum(node.right, sum, path, level + 1);

    /* Remove current node from path. Not strictly necessary, since we would
     * ignore this value, but it's good practice.
     */
    path[level] = Integer.MIN_VALUE; 
}

public static int depth(TreeNode node) {
    if (node == null) {
        return 0;
    } else {
        return 1 + Math.max(depth(node.left), depth(node.right));
    }
}

public static void findSum(TreeNode node, int sum) {
    int depth = depth(node);
    int[] path = new int[depth];
    findSum(node, sum, path, 0);
}

private static void print(int[] path, int start, int end) {
    for (int i = start; i <= end; i++) {
        System.out.print(path[i] + " ");
    }
    System.out.println();
}

My Question: According to the solution, the space complexity of this solution is O(n*log(n)). However, I feel like the space complexity should be O(log(n)) which represents the depth of recursion stack for the findSum() function. Why is my analysis wrong? Why is the space complexity O(n*log(n))?

Answer 1

The tree is not necessarily full - so it could have O(n) depth. As far as I can tell, the space complexity is O(n).

Answer 2

You're right; when the trees are balanced, this algorithm has space complexity of O(log n). (Note that the solution you posted is for a different problem than the one you wrote—it's for finding only paths that go down the tree.) Maybe the answer in the book was misprinted. If the book truly doesn't mention whether they're dealing with balanced or unbalanced trees, or where the paths can go, misprinted this answer, and contains no explanations for how they derived their answers... come on, you should be able to find a much better book than this to study algorithm complexity from.

Analysis

We can set aside from now if the trees are balanced by saying the depth of the tree is d, which is O(log n) if balanced, or O(n) if not.

There are 2 things in this algorithm that use space: the stack space used, and the array that is allocated. That int[] object has a size of depth(node), and is allocated exactly once, in the single call to findSum(TreeNode, int), so its space usage is O(d).

When findSum(TreeNode, int) calls depth(node), the stack frames will look like this:

[findSum(TreeNode, int)] [depth] ... [depth]

The furthest depth() can recurse is the depth of the tree, so the stack usage here is O(d).

Next, depth() finishes, and we call the recursive findSum(TreeNode, int, int[], int).

This function doesn't allocate any new memory, and it recurses to the depth of the tree just like depth(), so the stack usage here is also O(d).

So the maximum stack usage at any time in this algorithm is O(d), which plus the O(d) space used by the allocated array, gives us a final answer of O(d), which is O(n) in the general case, or O(log n) if the tree is balanced.