Lower Bound: More Analysis
Since we are working on a lower bound, in any tree, we must find the longest path from root to leaf. This is the worst case.
The most efficient algorithm would minimize the length of the longest path.
This happens when the tree is as close as possible to a complete binary tree