search
Log In
1 vote
427 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$
in Programming
edited by
427 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

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

Magma please add link of above diagram question

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.

Please log in or register to answer this question.

Related questions

1 vote
1 answer
2
299 views
AVL tree is created by inserting the keys 2, 6, 1, 5, 3, 4, 7 in the given order (Assume the tree is initially empty). Then the level order traversals of the tree would be. 2, 1, 3, 5, 4, 6, 7 3, 2, 5, 1, 6, 4, 7 2, 1, 3, 4, 5 ... even after knowing all the concepts. After 2 or 3 rotations I get stuck trying to figure out which way to rotate. Please help me with the proper steps in this question.
asked Jan 6, 2019 in DS Gupta731 299 views
0 votes
2 answers
4
355 views
Delete the key sequence [6,5,4] from the below AVL tree. How many rotations are needed to make it balanced AVL tree again?
asked Jan 31, 2018 in DS Meghaaa2612 355 views
...