Kth level print

#1

how to calculate time complexity of level order print by kth level by loop??

#2

@shampblocks hey complexity will be calculated in this way ki hmara code har node pr work krrha hai upto kth level and har node pr constant work horha hai that is printing ,so complexity will be no of node upto kth level* work at each node which is equal to no of nodes upto kth level,hope you get it.

#3

But how the worst case time complexity is n^2 if work is order of 1 in each node it should be n??

#4

@shampblocks hey in regard to this question each node is doing n work in case of skew tree ,so if there are n nodes and n work is done by each node than it will be n2.Skew tree is straight tree in one side means root ke right pr node uske right or ,similiarly so on so its height be n where n is node of nodes.

#5

So to print the kth level we have to reach till kth level doing work on k-1 nodes and doing work on k nodes?? So work will be done on the number of nodes in k-1 nodes and k nodes?? Total

#6

@shampblocks yes sahi keh rhe ho aap.

1 Like
#7

So total work will be work at k nodes + work at k-1 nodes?? Or it would be multilpy ??

#8

@shampblocks it will be multiply ,bro .

#9

But sir we are reaching in k-1 nodes not for each and every node in k level we are reaching k level nodes by doing work on k-1 nodes only once because to reach at 1 node at k level we need only 1 parent node in k-1 node?? Correct ke if I am wrong

#10

@shampblocks bro agr ap addition ki terms pehli node jo hai woh k-1 kam kregi agli node k-2 and so on ,generally ap aise soch skte ho ki skew tree is like array to hm har node ko select krrhe aur uspr k-1 then agli pr k-2 kamm horha hai jo inner loop krrhi hao to do loop ho gyi which are going to k so it will be in n2 or k2 .

#11

I am not talking about for loop part I was asking about only kth print not all level. Suppose I want to print only 3rd level the work will be nodes on 2nd nodes + nodes on 3 rd node??

#12

@shampblocks I m not clear with your qstn pls elaborate ,kth level pr print krna hai to complexity will be sum of work done by each node in kth level or it will be no of nodes at kth level *work by each node ,both are same .

#13

My question is if I want to print the 3 rd level of binary tree and it has height of 5 so to print the nodes at level 3 we have to first go through the 2nd level all nodes and after coming each and every node of third level I am printing so total work will be work at 2nd + work at 3rd ??

#14

@shampblocks hn sabhi nodes ka work add hoga ,1st root ka bhi hoga and 2 and 3rd.

#15

So in this case there is no. Multiply??

#16

@rishabhmahajan546 bhai multiply jo krrhe hai woh addition se hi arha hai agr apka har node pr kam same hai to hm no of nodeswork of one node kr skte hai : jaise isme har node ka work add horha hai ,to agr sab node ka work same hai to seedha hm no of nodework of each node jo usually sari nodes pr same hota hai ,multiplication is repeated addition bs yhi rule lgaya hai ek trah se .

1 Like
#17

Ohk sir thanks… …

#18

@shampblocks no problem

#19

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.