tree() method of the core Stream class needs to be optimized for time complexity
Closed this issue · 1 comments
Tell us about the bug
The tree() method of the Stream class inserts nodes at the beginning of a list inside a while loop, causing a potential worst-case time complexity of O(n**2), since the list.insert(0, node) operation shifts all items of the list by one position each time it is called.
Also, the function docstring needs to be corrected to reflect the implementation ordering of parent to child nodes (vs the child to parent currently specified).
What did you expect to see?
For large streams, this can cause a perf degradation.
What version of the library are you using?
Latest source on main branch.
Workaround?
The implementation can be fixed by first appending to the list as we traverse the ancestors of the current node, and finally do an in-place reverse on the list to obtain the expected ordering.
Anything else we should know?
Closed by #400 👍