How is that a binary tree with n! leaves has height omega (n log n)

Question

I came across this proposition that a binary tree with n! leaves has height omega(n log n). I am unable to understand how it is possible. I understand that height of a binary tree with n nodes is log n <= h <= n, i.e the height is at least log n (in case of complete binary tree), but I do not see a hint as to how the above proposition could be true or proved correct.

Any suggestions?

Answer 1

You have already stated that the lower bound for a binary tree with n nodes is log n. It is a well known fact (Stirlings formula), that log(n!) is approximately n log n. See for example here for a derivation.

A tree with n! leaves and minimal height has approximately 2n! nodes. This gives log(2n!) = log 2 + log(n!) approximately log 2 + n log n which is in omega(n log n)