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?
