Trees [What is the minimum possible depth of T]

Question

I just wanna know how can i get the min with certain number of nodes. Who can explain how to find the min 

 

 

Consider a binary search tree T with 5 nodes.

What is the minimum possible depth of T?

 

 

IF  a binary search tree T with 5 nodes.

What is the minimum possible depth of T?

 

thank u in advance!

Answer 1

The maximum number of nodes in a depth d binary tree is 2^d+1- 1, which happens for a full tree. Take the inverse of this to get the answer.

 

2^d+1 - 1 = n

 

d = log₂(n + 1) - 1

 

More precisely, we must take the ceiling, since we can't have a fractional depth. Thus the minimum depth of a tree with n nodes is

 

d = ⌈ log₂(n+1) ⌉ - 1

 

For 5 nodes we get a minimum depth of

 

d = ⌈log₂ 6⌉ - 1 = ⌈2.58...⌉ - 1 = 3 - 1 = 2