Question

Problem 3

Given a BST with N nodes, how many tree shapes are there with height N-1? Explain your reasoning.

Problem 4

Given a BST with N nodes, how many tree shapes are there with height N-2? Explain your reasoning .

Problem 5

Consider an empty 2-3 tree. Draw the tree after each of the following operations is executed:

insert 0, insert 9, insert 2, insert 6, insert 7, insert 3, insert 8, delete 2, delete 6

Answer 1

Problem 3

Answer :

Given a BST with N nodes ,

then the maximum height of that tree will be N-1.

given that height is N-1 , then it means all nodes will have only one child like a chain structure .

the total number of Binary Tree possible with N nodes = (^2NC_N) / (N+1)

Problem 4

Answer :

Given a BST with N nodes , and height is N-2

The minimum depth of a binary tree is [ log₃n ] and the maximum depth is N-2.

So in each level there will be  [ (^2NC_N) / (N+1) ] / [ (N - 2 ) - ([ log₃n ]) ] nodes.

Problem 5