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.
According to wikipedia. A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as.
Karim ElsheikhKarim Elsheikh
14433 gold badges55 silver badges1313 bronze badges
4 Answers
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
Joachim IsakssonJoachim IsakssonCEIL(log2(n+1))-1
.146k1818 gold badges214214 silver badges247247 bronze badges
You do not have to do a CEIL(log2(n+1))-1.
For a COMPLETE binary tree, the answer is simply:FLOOR(log2(n))
- 1 node gives 0
- 2 nodes gives 1
- 3 nodes gives 1
- 4 nodes gives 2
- 5 nodes gives 2
- 6 nodes gives 2
- 7 nodes gives 2
- 8 nodes gives 3
- ...
- 15 nodes gives 3
- 16 nodes gives 4
- ...
KelvinKelvin
I guess you can use the formula offered by Joachim or simply do floor log(h)... that is the best case you can do for any binary tree... thus if you tree for example is full you would not be able to say that this is necessarily true ... Also remember that in CS pretty much every log you encounter is of base 2
doubleOKdoubleOK
N is the number of nodes, h is the height of a complete binary tree:
2**h <= N < 2**(h+1)
=> h <= ln2(N) < h + 1 // See floor definition in wikipedia
=> h = floor(ln2(N))
The first inequality represents the fact the number of nodes of a complete binary tree with height h is superior to the number of nodes of a complete binary tree with height (h - 1) and at the same time is inferior to the number of nodes of a full tree with a height h, plus 1. Here is the math:
N_FULL_TREE(h - 1) = 1 + 2 + 4 + ... + 2**(h - 1) = 2**h - 1
N_FULL_TREE(h) = 1 + 2 + 4 +... + 2**h = 2**(h + 1) - 1
=> N_FULL_TREE(h - 1) < N_COMPLETE_TREE(h) <= N_FULL_TREE(h)
=> N_FULL_TREE(h - 1) + 1 <= N_COMPLETE_TREE(h) < N_FULL_TREE(h) + 1
=> 2**h - 1 + 1 <= N(h) < 2**(h + 1) - 1 + 1
=> 2**h <= N < 2**(h+1)
2**h <= N < 2**(h+1)
=> h <= ln2(N) < h + 1 // See floor definition in wikipedia
=> h = floor(ln2(N))
The first inequality represents the fact the number of nodes of a complete binary tree with height h is superior to the number of nodes of a complete binary tree with height (h - 1) and at the same time is inferior to the number of nodes of a full tree with a height h, plus 1. Here is the math:
N_FULL_TREE(h - 1) = 1 + 2 + 4 + ... + 2**(h - 1) = 2**h - 1
N_FULL_TREE(h) = 1 + 2 + 4 +... + 2**h = 2**(h + 1) - 1
=> N_FULL_TREE(h - 1) < N_COMPLETE_TREE(h) <= N_FULL_TREE(h)
=> N_FULL_TREE(h - 1) + 1 <= N_COMPLETE_TREE(h) < N_FULL_TREE(h) + 1
=> 2**h - 1 + 1 <= N(h) < 2**(h + 1) - 1 + 1
=> 2**h <= N < 2**(h+1)
Baroudi SafwenBaroudi Safwen