educative.io

Educative

Reverse Level Order traversal

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…

Hi @Amit_Gupta

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.