Help required regarding a question involving Complete Binary Tree

Правка en2, от white_sage, 2016-09-05 00:53:48

I recently gave a contest a contest hosted by MNIT on codechef. There was a question -- (https://www.codechef.com/INSQ2016/problems/INSQ16C)

It basically gives a complete binary tree and q queries and in the worst case you would have to traverse the complete binary tree q times.

My question is what is the time complexity to traverse a complete binary tree with n nodes, is it O(n) ( because there are n nodes to visit) or is it O(logn) because the height of that tree is logn.

The constraint on number of nodes is 10^5 and number of queries is 10^5 as well.

My solution which is basically( queries * time for tree traversal) passes in the given time.But I want to ask, is it because of weak test cases(which I suspect, is really the case!) or was it really correct?

My solution — (https://www.codechef.com/viewsolution/11367435)

Can anybody clear this up for me?Thanks

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский white_sage 2016-09-05 00:53:48 45
en1 Английский white_sage 2016-09-05 00:48:19 916 Initial revision (published)