The Gateway to Computer Science Excellence

+4 votes

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?

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

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?

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

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?

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 :)

It is arranged according to direction

values are to suggest , which direction to go

I thought like normal binary tree

thanks for correction :)

+2

for more intuitive ..you can relate from these questions

https://gateoverflow.in/3588/gate2006-it-45

https://gateoverflow.in/2756/gate1996_4

https://gateoverflow.in/3588/gate2006-it-45

https://gateoverflow.in/2756/gate1996_4

52,215 questions

60,035 answers

201,259 comments

94,722 users