How will be the time complexity of the code will be affected if the tree is not a skew tree?

#1

If the tree is not a skewed tree, then time complexity is going to be the O(height), so, for printing till Level 0 to Level H, the time complexity will also be O(N^2), so what is the difference in case of a skewed tree? Either way, we will be printing each level till the height of the tree whose upper bound will also be O(N^2). Please clear me if I’m wrong somewhere.
Thanks.

#2

didn’t unserdtand ur question can u gave a example
Futhur more the time complexity for traversing the normal tree is o(n) as u r visiting every node only once so it didnt make any problem wheather is a skew tree or not

#3

Yeah, this is what I was asking. Be it a skew or normal Binary tree. Either way the time complexity is going to be O(N^2), isn’t it?

#4

ya it remain same but O(n)

#5

Will it be O(N^2) if I go recursive way, like discussed. Where we find the height first, then for each level we call the PrintKthLevel() function?

#6

i am talking about simple pre post ino traversal
for that u visit eaxh node once

#7

@phantom can you please tell me that while printing the level order of a tree, recursive way. Where we first find the height of the tree and then use a loop from i = 0 to i <h ,for printing each level. So, what will be the time complexity of this approach in worst case.

I meant to ask this.

#8

Please refer to this.
How will be the time complexity of the code will be affected if the tree is not a skew tree?

#9

there is nothing to do with recursion in level order printing u can do it by iteratively using a stack and it will can also done in 0(n)
but if u do using recursion finding the height of the tree then u go at each level and visit all the node the complexity will be o(H*n)