closed by
273 views
–1 votes
–1 votes
closed with the note: Duplicate
When searching for a key value 50 in a BST, nodes containing key values 10,30,40,70,90,120.150.175 are traversed in any order . The number of different orders possible in which these key values can occur in search path from the root to the value containing 50 are ________
closed by

1 Answer

2 votes
2 votes
Howmany are grater than 50 ?

175,150,120,90,70 ===> 5 elements

note that in BST, if you are accessing a grater value than searching element, then next time you can't visit the node which is grater than the previous visited nodes.

i.e., on searching 50, if you visit 120 first then you can't visit either 150 or 175 in further searches.

( Think Why this is true, if you didn't get take a set of sample elements analyse it. )

So, 175 --> 150 ---> 120 ---> 90 ---> 70 should be visited in the order.

 

Howmany are less than 50 ?

10,30,40 ===> 3 elements

note that in BST, if you are accessing a lesser value than searching element, then next time you can't visit the node which is less than the previous visited nodes.

i.e., on searching 50, if you visit 40 first then you can't visit either 30 or 10 in further searches.

( Think Why this is true, if you didn't get take a set of sample elements analyse it. )

So, 10 --> 30 ---> 40 should be visited in the order.

 

Think this are transactions in DBMS, T$_1$ contains 5 and T$_2$ contains 3

Total orders possible = $\frac{(5+3)!}{5!.3!}$ = 56

Related questions

2 votes
2 votes
3 answers
1
0 votes
0 votes
1 answer
2
Shankar Kakde asked Jan 10, 2019
255 views
1 votes
1 votes
1 answer
3
Shadan Karim asked Dec 29, 2018
1,216 views
The height of a binary tree is defined as the number of nodes in the longest path form the root node to the leaf node. Let X be the height of complete binary tree with 25...