Solution to 10.12 (Java) is not space efficient and probably not O(n)

[damluar]

The solution creates a new object (linked list) for each node in the tree. Although it will be garbage collected quite soon, it’s still inefficient.
Looking at the LinkedList code, each addAll() transforms the list we want to add to an array and iterates over it, adding elements to the current list. It’s definitely not O(1) operation and we are doing it n times. I would guess it makes the whole algorithm O(n^2).

I’m curious why you changed the solution when going from C to Java. The C solution uses a helper function and is simple and efficient.

[tsunghsienlee]

Hey,

I just checked the addAll() implementation of LinkedList in Java and it actually is O(n) operation instead of O(1). Originally I thought it would be similar to splice() for list in C++; however, it is not that way. Therefore, I decide to use the old function which we pass parameter and then add leaves there.