Suppose a binary tree with $n$ levels and exactly $2^n-1$ nodes.

The nodes are random and their value does not determine their position in the tree at all. This isn't demonstrated in the picture, because I couldn't find a better image to use.

The task is to find the path to a given node. Since the nodes are random, we'd have to visit each node until we find the target. This should be $O(2^n)$ with the best case being $\Omega(1)$ (the target node is the root node). The output is at most an $n$-bit value, each bit specifying whether to traverse the left or right child node. When there are no more bits to be read, we know we've reached the target node. Therefore, the output can be read and verified in $O(n)$. Are there any flaws with this?

  • $\begingroup$ Your problem is in P. $\endgroup$ – Yuval Filmus May 29 '18 at 6:25

No, it doesn't. Your input size is exponential in terms of n. So the proper way to look at it would be to define k=2n-1 and solve the problems in terms of k.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.