Check if a binary tree is a perfect tree
Assuming you are given the root and nothing else, this problem has a lower bound of $\Omega(n)$.



An informal proof:

Consider an adversary who creates a perfect tree of height $h$ and size $n$. Now this adversary also has one extra node whose parent has yet to be determined. 

The adversary, being sneaky, doesn't determine the parent of this node until you've checked every other node in the tree. To be more precise, the parent of this extra node will be the very last leaf node you check. 

Clearly this will take $\Omega(n)$ time for any algorithm to determine this adversary has an imperfect tree.



That being said, you could find algorithms with a better expected time. For example, you could try non-deterministic algorithms such as random walks of the tree, then compare the lengths of these random walks to give a probability of perfectness. Although in any case, you won't do better than $O(n)$.