0% completed
For the python solution, is the time complexity mainly taken from the inner for ...
Richard Yuan
Mar 27, 2022
For the python solution, is the time complexity mainly taken from the inner for loop? I understand that the inner for loop will have to perform an iteration for each node in the tree, but I am confused on how to factor in the outer 'while queue' loop into the time complexity calculation. Any help would be appreciated!
0
0
Comments
Design Gurus4 years ago
The 'while' is for processing 'tree levels' whereas the 'for' loop is processing nodes of the current level.
If a tree has '3' levels as is the case with first example mentioned, the 'while' loop will iterate three times. In the first iteration, the 'for' loop will ite...
Richard Yuan4 years ago
I see that makes sense! I believe my misunderstanding stems from my time complexity calculations usually taking into account each loop as its own O() term, which is what tripped me up here. So my time complexity was O(N) + O(M) where M is the number of levels. Is there ...
Salah Osman3 years ago
O(logn) for the while loop, O(n) inner for loop. So O(logn+n) --> O(n)
On this page