+1 vote
214 views
Consider an empty binary search tree of height $-1.$We need to fill the following sequence of numbers in it $: 11, 12, 13, 14, 15, 16, 17.$The number of ways in which the numbers  can be inserted in an empty binary search tree, such that the resulting tree has height $6,$ is _____________

$A)2$                        $B)4$                          $C)32$                     $D)64$

edited | 214 views
+1

No this is not a Binary Search Tree,Because right of 14,13 not come, it violate the Property of BST.

0

Is it possible or not

0
How it is not??? Explain
0
Yes
0

Because

14

\

15   is true

but

14

\

15

/

13

Violate the BST Property.  13 not comes,right of 14

0
Yes thanks but I'm getting other BST other than increasing or decreasing
0
Yes,i also get but i'm not able to find all $2^{6}$
0

mitesh kumar  then you're right

ans D ) 64

+1
0
I think it will work like this -
Take 1 from 11 or 17 suppose taken 11 then for next level take one from 17 or 12 let say 12 taken then for next 17 or 13,13 or 16 if 17 taken then 14 or 16 then 16 or 15 and lastly if 16 taken then 15...Please comment if I'm going in wrong direction
0

Soumya Tiwari  yes I'm also think in that way

0

In Binary Search Tree all Sorted elements in ascending order like $11,12,13,14,15,16,17$ gives always INORDER TRAVERSAL of the BST.

With $7$ nodes Number of unlabeled BST Possible are $429$.To get Inorder so we can assign the number in the all BST and get $429$ BST with In order $11,12,13,14,15,16,17$, But some tree doesn't have a height $6$, So we can subtract these BST and get the answer, but I'm not able to find the BST, which doesn't have height $6.$

can anyone help me?

0

Lakshman Patel RJIT

you choose very very tough path bro... don't follow this approach

0
Yes, it is very tough, how can I solve this type of question, to think something?
0

This is really nice approach

0
thanks Brother
0

+1
the link in the above comment, you can check it out!!
0
okk :)

miss that comment
0
Given that, height of empty tree is 1 then it is 5*(2^5) = 5*32 = 160

If height of empty tree is 0, then it is 2^6 = 64

Note that, generally height of empty tree or height of root is convey same thing.