The reasoning used to generate the worst-case space complexity for balanced binary trees makes sense. If it’s balanced, root to leaf paths will be no more than logN and the maximum number of leaves given N nodes is N/2. O(N/2 * logN) = O(N*logN).
I’m good with that. However, they offered no explanation for why it’s the same for unbalanced binary trees. Given 7 nodes, I can create a binary tree that will require more space to store the output array of root to leaf paths than the full binary tree given in the example.
It’s akin to saying, the longest path possible is N and the maximum number of leaves is N/2 so our space complexity is O(N^2). However we know if the binary tree has a root to leaf path of length N then it will only have one path. Although this reasoning actually makes more sense than the one provided.