My advice is don't guess. Do the math.
To print level L of a perfectly balanced tree, you will traverse 2^L
-1 nodes.
The outer loop that prints levels 1 .. H will therefore traverse
sum_{L=1..H} (2^L - 1) = 1 + 3 + 7 + ... 2^H - 1
Let N = 2^H - 1 be the number of nodes in the tree. Then
sum_{L=1..;H} (2^L - 1)
= sum_{L=1..H} (2^L) - H
= 2^(H+1) - 2 - H
= 2 N - log(N+1)
= O(N)
On Nov 20, 7:13 am, Ankuj Gupta <[email protected]> wrote:
> I guess its NlogN for balanced tree as it is traversing N nodes for H
> times ie the height of tree which is logN for balanced and N for
> skewed tree. So it should be Nlogn and N^2
>
> On Nov 20, 9:27 am, tech coder <[email protected]> wrote:
>
>
>
> > @ sravanreddy001
> > complexity is O(N^2) whether tree is balanced or not doesn't matter
> > For each level it's visiting elements. all elements upto n-1 level .
> > i dont know from where u got the concept of logn , the code is not
> > making any decision to go in left or right , it is going in left and right
> > both , so how it is nlogn.
>
> > On Sun, Nov 20, 2011 at 3:12 AM, sravanreddy001
> > <[email protected]>wrote:
>
> > > Its NlogN if balanced.. Else N^2
>
> > > For each element it's visiting at most log N elements.(assuming balanced)
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To view this discussion on the web visit
> > >https://groups.google.com/d/msg/algogeeks/-/hVQH5EtOfK4J.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected].
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > *
>
> > Regards*
> > *"The Coder"*
>
> > *"Life is a Game. The more u play, the more u win, the more u win , the
> > more successfully u play"*- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
