The Gateway to Computer Science Excellence

+2 votes

Number of ways we can insert 5,6,9,10 in the nodes of BST, such that height of BST is either 2 or 3?

0

I think it is the Catalan no.only because we cannot have a BST with height>3 or height<2 with 4 nodes. Only possible heights are 2 and 3 only.

0

can u plz explain? It was a gate question modified (I will give the link)

I got less number of trees :(

I got less number of trees :(

0

I see no possible sequence of insertion of any 4 distinct nodes in BST which would lead to a BST of height other than 2 or 3. Is there any?

+1

Yes that is right.. But no. of ways of insertions is asked..I think it is 4! because for each of the arrangement there is one BST (may not be unique). More than 1 way of insertion may lead to same BST but that doesn't mean that we should ignore that arrangement.. We need to find the no. of ways of insertion and not no. of unique BSTs.

+1

can anyone answer this please The number of ways in which the numbers 1,2,3,4,5,6,7 can be inserted in an empty binary search tree, such that the resulting tree has height 5, is ____

+3

srestha I didn't multiply it with 2.

I was saying we can arrange 4 keys in 4! ways and each of these ways can be considered as an order of insertion. So 24 ways of insertion ( though may give rise to duplicate BSTs) but that is not our concern here.

+1

@MiniPanda, explanation is Correct for this answer...

i hope no need any further arguments on this question.

i hope no need any further arguments on this question.

+1

yes 4! should be ans, as there is only height 3 or 2 possible. any other height not possible with this node

totally different type ans

I take it from

+1

@minipanda please explain it a bit more

Actually for both this arrangement the tree is same but order of insertion is different so are you talking about this thing

Here the insertion order is different but trees are same so if I count the trees then it will be 14 but insertion order is different so that are total 24

Please correct me if i am wrong

+1

can anyone answer this please The number of ways in which the numbers 1,2,3,4,5,6,7 can be inserted in an empty binary search tree, such that the resulting tree has height 5, is ____

srestha, Vikas Verma, Shaik Masthan, Rishav Kumar Singh, Shivani gaikawad Please check

To get BST of height 5, max( height of left subtree,height of right subtree) should be 4 [Height of tree= 1 +max Height of subtree]

There can be only two possible roots for such BST -> 2 and 6.

If you fix 2 as the root the left subtree gets 1 and the right subtree gets (3,4,5,6,7). Now treat this as a new problem (like the one in the link you provided).

"The number of ways in which the numbers 3,4,5,6,7 can be inserted in an empty binary search tree, such that the resulting tree has height 4"

This will be 2^4=16.

Now '1' can be inserted at anytime in between the insertions but 2 has to be inserted at first. So 2_3_4_5_6_7_. So there are 6 places where 1 can be inserted.

So, 6*16 =64.

Again fix root as 6. The right subtree will get 7 and the left will get (1,2,3,4,5). Following the same method again we get 16 BSTs.

Here 7 can be inserted at any time but 6 has to be the first one to be inserted.

Again there are 6 possible spaces where 7 can be inserted.

So 6*16=64.

64+64=128.

But if the number of unique BSTs with height 5 is asked then it should be 16+16=32 because insertion of 1 for 1st case and 7 for 2nd case results into the duplicate BSTs.

Do let me know if there is any mistake.

0

0

MiNiPanda ur above answer for

is wrong ...

u rsaying that root can be only 2 and 6 but is not necessary ...

lets take 7,5,6,4,3,2,1 in this root is 7 and height is also 5 according to conditions of bst

0 votes

I think answer will be 14

We have 5,6,9,10

Now if we take 10 at root then 5 trees will be there 4 with height 3

and 1 with height 2

If we take 10 then for height 3 -4 trees

Similarly for 5 if it is selected to insert at root node then 5 trees possible

Now if we insert 6 at root node then definitely 5 will be it's left child so 2 trees are possible by arranging 9 and 10 as it's right child

And same will be for 9 also two trees are possible with height 2

H(3)4+H(3)4+H(2)1+H(2)1+H(2)2+H(2)2

We have 5,6,9,10

Now if we take 10 at root then 5 trees will be there 4 with height 3

and 1 with height 2

If we take 10 then for height 3 -4 trees

Similarly for 5 if it is selected to insert at root node then 5 trees possible

Now if we insert 6 at root node then definitely 5 will be it's left child so 2 trees are possible by arranging 9 and 10 as it's right child

And same will be for 9 also two trees are possible with height 2

H(3)4+H(3)4+H(2)1+H(2)1+H(2)2+H(2)2

52,215 questions

60,035 answers

201,258 comments

94,722 users