##### Binary search tree

Consider file system stores records as per binary search tree principles. If the postorder traversal of records is given by 2, 4, 3, 9, 13, 7, 6, 17, 20, 18, 15. The expected number of comparisons when we randomly request one of the records (upto 2 decimal places) is _____.

3.09

How?? Please give complete solution

Firstly with the help of pre order given and since it's a binary search tree so inorder traversal of this tree will be 2,3,4,6,7,9,13,15,17,18,20 .With the help of inorder and pre-order construct a binary search tree then at 0th height of tree there would be one comparison and 1 element at 1 height 2 comparsion and 2 element at height 3,4 element and 3 comparisons and so on.. Now to calculate expected no of comparisons=1*1/n +2*2/n and so on