The Gateway to Computer Science Excellence
+3 votes
174 views
When searching for the key value 30 in a binary search tree, nodes containing the key values 10, 20, 25, 35, 70, 80, 90, 100 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root node containing the value 30?

-----------------------------------------------------------------------------------------------------------------------------------------

Solution is

1)  8!/(3!*5!) (here tree permutation is done based on non root node of the tree as a whole)

or

2)  it could be

3*2*5*4*3*2 (here division is based on left subtree and right subtree

where 3*2 is permutation for left subtree and 5*4*3*2 is permutation of right subtree)

---------------------------------------------------------------------------------------------------------------------------

what is difference between solution 1) and solution 2)?

why in both case answer is different?
in DS by Veteran (116k points) | 174 views
0
srestha can you explain little bit more ur 2nd solution what exactly you are doing
0
@Sonam
we know, 3 nodes in left subtree
Now,among 10,20,25 take any one as root , so choosing will be 3C1 ways
Now,among other two nodes , take any one choose as 2nd node
Likewise do for other 5 nodes too
I will show u in picture
0
But can u check the 1st solution too

We do 8! when we  combine all 8 elements at a time

Here, we cannot combine all 8 elements

we have to combine 3 elements and 5 elements seperately

as all elements are distinct

right?
+1

yes ur 1 st sol correct .. 

its like we have to search 30 , its bigger than 10 20 25 but smaller than 35 70 80 90 100 and we have to traval all elements rt .. suppose 20 is root and 25 comes then i will never cross 10 in searching of 30 becoz it will search only at right side of (bigger side ) root .. so there should be only 1 way so i can write in this way sssvvvvv now apply simply permutation ..

you can see this https://gateoverflow.in/3462/gate2007-it-29(better explaination ) 

for 2nd sol post your sol pic 

0
yes, thanks

It is arranged according to direction

values are to suggest , which direction to go

I thought like normal binary tree

thanks for correction :)
+1
for more intuitive  ..you can relate from these questions   
https://gateoverflow.in/3588/gate2006-it-45
https://gateoverflow.in/2756/gate1996_4
+1
yes probe sequence

I understand

Please log in or register to answer this question.

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
50,666 questions
56,167 answers
193,841 comments
94,042 users