Question

(a) How many different shapes can a BST be in, if its height = 3?

(b) Find the average depth of a node in a BST of height = 3, assuming that every shape of the BST is equally likely.

~Answer might be 1.5

(c) Give a strong argument as to whether all BST shapes at height = 3 are equally likely.

I would like to understand how the answers are calculated i.e. what formula please.

Answer 1

a) How many different shapes can a BST be in, if its height = 3?

b) Find the average depth of a node in a BST of height = 3, assuming that every shape of the BST is equally likely.

c) Give a strong argument as to whether all BST shapes at height = 3 are equally likely.

Suppose the height of a BST is h, then total number of nodes nis

n = 2h+1 -1(for maximum number of nodes)

n = h + 1 for minimum number of nodes)

Now, if we consider for minimum numbers of nodes, then for h = 3

n= (h+1) = (3 +1) = 4

Now, with 4 nodes, total

(2n)! - numbers of BST of different shapes are possible.

putting n = 4 at the above equation we get

(2 * 4)! (4 + 1)!*4! 8! 5!*4! = 14

So, 14 different shaped BST is possible.

for average depth of the node with minimum nodes = n = (n + 1) = (3 + 1) = 4

total depth for all n nodes =>i*1 WI

now for depth = height = h = 3, total depth is

> i*1=0*1+1*1+2*1 +3* 1 = 1 + 2 + 3 = 6

6 = 1.5 average depth = total_depth 6 no of nodes n+1 =

if we consider maximum number of nodes, then n = 2h+1 - 1 if we consider minimum number of nodes, then n = h + 1 for maximum number of nodes, maximum possible BST will be (2n)! = 9694845 where, n = 2h+1 - 1 = 23+1 - 1 = 15 (n + 1)! *n! again for maximum number of nodes, total depth = total depth = 31.26 i + 2 for h = 3 it will be i* 21 = h. 2h+1 - 2+1 +2 = 3.24 -24 +2 = 48 - 16 + 2 = 34 n will be n = 2h+2 - 1 34 So average depth = 2h+1 34 5

So if we consider maximum or minimum number of nodes, according to that total number of BST

and the average depth will be changed. here in the a) b) we worked with minimum numbers of nodes

forn = (h + 1), but at c) we show it with maximum 2h+1 - Inumber of nodes.