CODEWITHSUNDEEP
data-structurestree
NotSure
NotSure

Reputation: 681

What is the minimal depth of a 4-ary tree with n nodes?

The question is:

What is the minimal depth of a 4-ary tree with n nodes?

I can't find the correct log that is the answer, I know that for n = 1 the depth is 0, if 2 <= n <= 5 it is 1, if 6 <= n <= 21 it is 2

Thanks in advance!

Upvotes: 0

Views: 1521

Answers (1)

avim
avim

Reputation: 1019

That is a math question.

Lets find the relation f between the height h and the number of nodes n in a full tree. I'll to it with recursion.

n = f(h). The base is easy, as you said: f(0)=1.

We can see that each level contains exactly 4^i nodes, where i is the distance from the root. So, after summarizing all levels we have:

f(h) = 4^h + f(h-1) = 4^h + 4^(h-1) + ... 4^1 + 4^0 = (4^(h+1)-1)/3 =n [sum of geometric series]

Isolating h:

h = log_4(3n+1) - 1 and you should take the ceil() of that, because you want it to apply on non-full trees as well.

Generalization for k-ary is easy now, as:

f_k(h) = (k^(h+1)-1)/(k-1), so h = ceil(log_k((k-1)n + 1) - 1)

Upvotes: 1

Related Questions