Space complexity of 9.9 solution

#1

The book states that the proposed solution has O(m) space complexity, where m is the maximum number of nodes at any single depth. How can the complexity be O(m), when the result contains all tree nodes, so the space cannot be less than O(n) by definition.

0 Likes
#2

The space complexity here does not include the space for output, mostly we don’t consider the space of input either. Otherwise, you probably won’t see any O(1) space complexity algorithm in the world :stuck_out_tongue:

Let me know if you have any other question, and I am happy to discuss with you.

0 Likes
#3

I agree, but the brute-force approach collects result into an array and the book says that it has O(n) space complexity. According to your logic above, it should be O(1) then.

0 Likes