What is the height of a complete binary tree with N nodes?

Question

What is the height of a complete binary tree with N nodes? I'm looking for an exact answer, and either a floor or ceiling value.

Answer 1

It's CEIL(log2(n+1))-1

• 1 node gives log2(2) = 1
• 3 nodes gives log2(4) = 2
• 7 nodes gives log2(8) = 3
• 15 nodes gives log2(16) = 4
  ...

EDIT: According to wikipedia, the root node (rather un-intuitively?) does not count in the height, so the formula would be CEIL(log2(n+1))-1.