Made Easy test series DS

Question

The number of binary search trees possible with 12 keys, when keys 1, 2, 3, 4, ........ 12 are inserted into empty Binary Search Tree with condition such that 4  is the root of binary search tree and 8 is immediate right child of 4 are ________.

Comments

okay

---

@Shaik Masthan

tell me one thing if we comment on a previous year question, then do all the users get to know that doubt( i mean those who have tag like BOSS,LOYAL,VETERAN ) or only those users are notified who have commented for that question!!

because there are many questions for which we have doubt and we comment there only means on that question only, but those who have commented earlier on that question have not seen the site since many days;

then what to do in such a situation??doubts remains doubts

for ex , this question (link given below) is asked 2 times, for 2016, those who have commented have not seen the site since 3 months; and for 2017 one, no comment is there!!

https://gateoverflow.in/113154/ugcnet-dec2016-ii-12

https://gateoverflow.in/158425/ugcnet-jan2017-ii-12

---

only who have comment before you comment get notification... Remaining doesn't get notification..

Answer 1

check this image..

Comments

great explaination, thanks @Shubham Shukla

Answer 2

note that given that it is a binary search tree,

root is fixed to 4 and root immediate right child is fixed to 8, therefore

total elements less than 4, should be left side of root ==> there are 3 elements  ( 1, 2, 3) ===> 5 tree structures we can get

 total elements grater than 8, should be right side of node 8 ==> there are 4 elements ( 9,10,11,12 ) ===> 14 tree structures we can get

therefore total elements grater than 4 and less than 8, should be left side of node 8 ==> there are 3 elements ( 5,6,7 ) ===> 5 tree structures we can get.

 

For required a complete Binary Search Tree structure, we have to these three process ===> 5*5*14 = 350 possible structures possible

Answer 3

///now rest of the element 5,6,7,9,10,11,12 they can also come in order , s0 it becomes = 7! =5040

this line is false as suppose u take 12 after 8 ,then 12 in right of 8 after that u insert 5 then as it insert at leaf 5 <12 and 5 also <8 but it is in right of 8 so false statement

Insertion of a key 
A new key is always inserted at leaf. We start searching a key from root till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node

same case for 1,2,3,8

see JUST REMEMBER WE ALWAYS INSERT NODES AT LEAF LEVEL NOT UPPER .

so if u inert 8 then 8 is leaf then u r of no good again.

so total ways according to me is  

5 ( for 3nodes total  5 bst ) * 5 * 14 = 350