723 views
6 votes
6 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?

1 Answer

Best answer
23 votes
23 votes
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
Answer:

Related questions

0 votes
0 votes
1 answer
1
Arjun asked Oct 10, 2016
291 views
The following numbers are inserted into an empty binary search tree in the given order: 1000, 452, 131, 15, 85, 75. What is the height of the binary search tree (the heig...
0 votes
0 votes
3 answers
2
Arjun asked Oct 10, 2016
620 views
Consider a complete graph of 10 vertices. The minimum no. of edge removals required to make the graph disconnected is ______
0 votes
0 votes
2 answers
4
Arjun asked Oct 10, 2016
524 views
Consider the following declaration of a two dimensional array in C:char a[1000][40];Assuming that the main memory is byte addressable and that the array is stored startin...