Reverse Level Order traversal

[Amit_Gupta]

Not clear with the complexity. As the solution code inserting values at beginning of list at end why that is not considered while complexity analysis. Inserting at front would shift all the element and thus would lead to O(n^2) complexity.

Please help…

[aswad.sohail]

Hi @Amit_Gupta

@Amit_Gupta

As the solution code inserting values at beginning of list at end

There three types of insertions that are being done in this algorithm

1. Queue
   Insertion is maximum N/2
   a. One node in the first iteration
   b. Two nodes in the second iteration
   c. Three nodes in the third iteration
2. currentLevel (list)
   Insertion is maximum N
3. result (list)
   Insertion is again N/2

So cumulatively, the complexity will be N.

I hope I have answered your question. If there is still any confusion, then please respond to me. Thanks.