The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
138 views
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?
asked in DS by Veteran (100k points) | 138 views
0
@MiniPanda

why we multiplied by 2 every time?
0
i post my answer one more time with edit
+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.
+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

https://gateoverflow.in/39586/gate2016-2-40

+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

0
@shivani... Yes
+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 SinghShivani 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
@MiniPanda

rethink @Shivani's point

isnot 6,5,10,9 and 6,10,9,5 gives same tree?
0
Yes they will give same BST..As i already told more than 1 insertion order may result into same BST

1 Answer

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
answered by Active (4.3k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,455 questions
48,492 answers
154,715 comments
63,084 users