Check if a binary tree is a perfect tree

Question

I'm trying to write an algorithm to check if a given binary tree is a perfect binary tree, and of course with the lowest complexity.

I was thinking to calculate the height of the tree $h$ and the number of the nodes $n$, then if $2^{h+1} -1 = n$, it's a perfect tree. But then again, it's not very efficient.

The I thought to find the minimum tree height, and maximum tree height, and if they are equal, it's a perfect tree. But also this case, isn't much of improvement.

Any idea how to make it better?

Answer 1

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)$.