What's the worst-case space complexity for the All Paths Sum problem for an unbalanced tree?

Question

Here's the problem statement as stated on educative.io.

Given a binary tree and a number ‘S’, find all paths from root-to-leaf such that the sum of all the node values of each path equals ‘S’.

I understand the solution given to the problem and the time complexity portion. My confusion lies with the worst-case space complexity. The space complexity for the output array is calculated for a balanced binary tree and it's concluded that it's the same for an unbalanced binary tree without any explanation.

Here we have seven nodes (i.e., N = 7). Since, for binary trees, there exists only one path to reach any leaf node, we can easily say that total root-to-leaf paths in a binary tree can’t be more than the number of leaves. As we know that there can’t be more than (N+1)/2 leaves in a binary tree, therefore the maximum number of elements in allPaths will be O((N+1)/2) = O(N). Now, each of these paths can have many nodes in them. For a balanced binary tree (like above), each leaf node will be at maximum depth. As we know that the depth (or height) of a balanced binary tree is O(logN) we can say that, at the most, each path can have logN nodes in it. This means that the total size of the allPaths list will be O(N*logN). If the tree is not balanced, we will still have the same worst-case space complexity.

From the above discussion, we can conclude that our algorithm’s overall space complexity is O(N*logN).

Also, from the above discussion, since for each leaf node, in the worst case, we have to copy log(N) nodes to store its path; therefore, the time complexity of our algorithm will also be O(N*logN).

I drew out a couple of binary trees with 7, 8, 9, ... nodes and I'm able to create unbalanced trees that would require more space in the output array than it's balanced tree counterpart. Furthermore, the difference does not grow by a constant value.

Answer 1

Good for you, actually double-checking the reasoning instead of taking it on faith that it is correct!

The method of analysis for a balanced binary tree is correct for an unbalanced one as well. But the unbalanced one can have depth O(N). And therefore the maximum space is the number of paths times the depth, which is O(N) * O(N) = O(N^2).

For an unbalanced binary tree that reaches the worst case, we will create a tree all of those nodes have value 1 of size a power of 2. The first half the nodes are a straight line leading to the right. The other half are a perfectly balanced binary tree from the end of the first half. This tree will have O(N/4) paths of weight N/2 + log_2(N/2) and will indeed require O(N^2) space.

I would strongly suggest pointing out the mistake to them so that they can correct it.