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