in DS
468 views
5 votes
5 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?
in DS
by
468 views

1 comment

0
0

1 Answer

21 votes
21 votes
Best answer
Total permuations possible $=8!$.

In a BST, when we encounter a number larger than the searched key, it is not possible to encunter an even larger number again. Similarly for smaller ones. For example, while searching for 30, if we encounter 35, it is not possible to encounter 40 afterwards.

So, in the given question, 10-20-25 must be in order. So do, 100-90-80-70-35. Thus, no. of valid permuations

$$ = \frac{8!}{3!5!} = 56.$$
selected by
by

2 Comments

can you please explain the approach
0
0
Please explain the answer!!
0
0
Answer:

Related questions