edited by
38,906 views
172 votes
172 votes

When searching for the key value $60$ in a binary search tree, nodes containing the key values $10, 20, 40, 50, 70, 80, 90$ 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 to the node containing the value $60$?

  1. $35$
  2. $64$
  3. $128$
  4. $5040$
edited by

13 Answers

0 votes
0 votes
To find 60 in BST then there are two possible set i.e., greater than 60 and smaller than 60.
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35
0 votes
0 votes

Think: It is same as finding total number of bst possible for 7 nodes with only 1 leaf node.

Why only 1 leaf node?

Because nodes of search path can't have 2 children.only one child is allowed. If not then considered search path will not be valid anymore.try out!

Now solve !

Hint: for each node you have only two choices that is choosing either min(remaining nodes) or max(remaining nodes).so total possibility=2*2*2*2*2*2*1=64

If still not able to solve then Above thinking part is solved by experts in this platform search.

 

0 votes
0 votes
The answer is 7C4.

Searching for 60, we encounter 4 keys less than 60 (10,20,40,50) & 3 keys greater (70,80,90).

The four lesser keys must appear in ascending order while the three greater ones must appear in descending order otherwise some keys will be left out in the traversal.

Note that in the traversal, these lesser keys might not be continuous and can be separated by greater keys.

For eg: 10, 90, 20, 30, 80, 40, 70, 50

but the order of both groups of keys (lesser and greater) remains the same individually.

Now, out of total seven positions, the lesser keys acquire four positions which can be selected in 7C4 ways. Once we know the places of these four keys, the places of the three greater keys only have one permutation.

For eg: if we know that

10, _, 20, 30, _, 40, _, 50

Then there's only one permutation of places for 90, 80 & 70 which is place number 2, 5 & 7 respectively.

Therefore for each combination of lesser keys, there's a unique combination of greater keys.

So total combinations= 7C4*1 =35 ways

This ans was given on stack overflow, it crystal clear explanation.
Answer:

Related questions

62 votes
62 votes
11 answers
2
Ishrat Jahan asked Oct 29, 2014
28,960 views
Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collide...