white_sage's blog

By white_sage, history, 4 years ago, In English

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

Read more »

  • Vote: I like it
  • +4
  • Vote: I do not like it