248 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?
in DS | 248 views
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

I asked for no of ways
0
Oh okay.. I'm sorry :P

0
@MINIPanda, how did you find that, can you please explain?
0
First let srestha confirm the answer otherwise no use explaining it :P
0
haha, makes sense.
0
i am getting 12 only..... sorry not 12, it is 14
0
can u plz explain? It was a gate question modified (I will give the link)

I got less number of trees :(
0
sorry to all ... i also did no.of tress, not no.of ways
0
@Shaik u did right

I think
0
0

Vikas Verma What answer are you getting?

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.
+2

nice question  srestha mam

+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 ____
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 ____

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
0

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 ____

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
i think answer of above question like we have 7 nodes choose 6 out of it then it is 7C6 then arrange these 6 nodes like we have atree of height 5 in $2^5$ then out of these 6 nodes i can place node in left or right in 6 ways as 6 nodes

7 * 6 * $2^5$

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
by Active