Search code examples
binary-treelayerlogarithmexponential

Height of full binary tree

I just need confirmation that i´m right: A binary tree with 'e' layers has

(2^e)-1

elements. The other way around: A binary tree with 'n' elements has

log2(n+1)

layers...

Am i right?

Solution

  • It depends on how you describe the 'height' of your tree. Generally, a tree with only one element is said to be at height 0. The calculations are like this:

    The number of leaves in a full binary tree of height n is 2^n. The number of interior nodes in a full binary tree of height n is 2^n - 1.

    So a full binary tree with n layers will have a total of (2^n + 2^n - 1) elements. That turns out to be (2*2^n - 1) or simply 2^(n+1) - 1 elements.

    The other way around, a binary tree with n elements has a height of log2(n+1) - 1.