I understand intuitively why in a binary tree there are a minimum of floor(log2(n)) + 1 levels. I was wondering if there is an equivalently straightforward algorithm for the minimum number of levels in an n-ary tree. Say a full/complete ternary tree for example: my intuition tells me this would involve log3(n) somehow but I cannot figure it out.
1 Answers
You can find the formula for an m-ary tree by first checking what the maximum number of nodes is that you can store in a tree with degree m:
| levels | n |
|---|---|
| 1 | 1 |
| 2 | 1+m |
| 3 | 1+m+m² |
| 4 | 1+m+m²+m³ |
| ... | ... |
| k | 1+m+m²+...+mk−1 |
This is equivalent to
n = (mk − 1) / (m − 1)
This means that a tree with k levels has at least n = 1 + (mk−1 − 1) / (m − 1) nodes. Solve that to k:
n = 1 + (mk−1 − 1) / (m − 1)
n − 1 = (mk−1 − 1) / (m − 1)
(n − 1)(m − 1) = mk−1 − 1
(n − 1)(m − 1) + 1 = mk−1
logm((n − 1)(m − 1) + 1) = k − 1
logm((n − 1)(m − 1) + 1) + 1 = k
As n is here a minimum of nodes for k levels, we need to take the floor when n is free:
k = ⌊logm((n − 1)(m − 1) + 1)⌋ + 1
For binary trees, m=2, so that simplifies to:
k = ⌊log2(n)⌋ + 1
...which is what you already had.
For ternary trees, m=3, so then we get:
k = ⌊log3(2n − 1)⌋ + 1
Related