468 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?

### 1 comment

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.$$
by

can you please explain the approach